Advertisement
cosenza987

Untitled

Jan 18th, 2022
898
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.10 KB | None | 0 0
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC optimize ("unroll-loops")
  3. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. //THESE ARE LAST DITCH EFFORTS!!!
  5.  
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. const int mod = 998244353;
  11.  
  12. typedef long long ll;
  13.  
  14. ll addmod(ll a, ll b, ll m){
  15.     if(a >= m - b) return a + b - m;
  16.     return a + b;
  17. }
  18.  
  19. ll mulmod(ll a, ll b, ll m){
  20.     ll ans = 0;
  21.     while(b){
  22.         if(b & 1) ans = addmod(ans, a, m);
  23.         a = addmod(a, a, m);
  24.         b >>= 1;
  25.     }
  26.     return ans;
  27. }
  28.  
  29. ll fexp(ll a, ll b, ll n){
  30.     ll r = 1;
  31.     while(b){
  32.         if(b & 1) r = mulmod(r, a, n);
  33.         a = mulmod(a, a, n);
  34.         b >>= 1;
  35.     }
  36.     return r;
  37. }
  38.  
  39. bool miller(ll a, ll n){
  40.     if (a >= n) return true;
  41.     ll s = 0, d = n - 1;
  42.     while(d % 2 == 0 && d) d >>= 1, s++;
  43.     ll x = fexp(a, d, n);
  44.     if (x == 1 || x == n - 1) return true;
  45.     for (int r = 0; r < s; r++, x = mulmod(x,x,n)){
  46.         if (x == 1) return false;
  47.         if (x == n - 1) return true;
  48.     }
  49.     return 0;
  50. }
  51.  
  52. bool isprime(ll n){
  53.     if(n == 1) return false;
  54.     int base[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
  55.     for (int i = 0; i < 12; ++i) if (!miller(base[i], n)) return false;
  56.     return true;
  57. }
  58.  
  59. ll pollard(ll n){
  60.     ll x, y, d, c = 1;
  61.     if (n % 2 == 0) return 2;
  62.     while(true){
  63.         y = x = 2;
  64.         while(true){
  65.             x = addmod(mulmod(x,x,n), c, n);
  66.             y = addmod(mulmod(y,y,n), c, n);
  67.             y = addmod(mulmod(y,y,n), c, n);
  68.             d = __gcd(abs(x-y), n);
  69.             if (d == n) break;
  70.             else if (d > 1) return d;
  71.         }
  72.         c++;
  73.     }
  74. }
  75.  
  76. void factor(ll n, vector<ll>& v){
  77.     if (n == 1 || isprime(n)) return v.push_back(n);
  78.     ll f = pollard(n);
  79.     factor(f, v), factor(n/f, v);
  80.     sort(v.begin(), v.end());
  81. }
  82.  
  83. int main() {
  84.     ios_base::sync_with_stdio(false);
  85.     //cin.tie(nullptr);
  86.     map<long long, long long> cnt;
  87.     int n;
  88.     cin >> n;
  89.     while(n--) {
  90.         long long x;
  91.         cin >> x;
  92.         vector<long long> f;
  93.         factor(x, f);
  94.         for(auto e : f) {
  95.             cnt[e]++;
  96.         }
  97.     }
  98.     long long ans = 1;
  99.     for(auto e : cnt) {
  100.         ans = (ans * (e.second + 1)) % mod;
  101.     }
  102.     cout << ans << "\n";
  103.     return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement