Submission #846852

---

Source Code Expand

// tested by Hightail: https://github.com/dj3500/hightail
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <stack>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cassert>
using namespace std;
#define pb push_back
#define INF 1001001001
#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
#define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
#define mp make_pair
#define pii pair<int,int>
#define ll long long
#define vi vector<int>
#define SZ(x) ((int)((x).size()))
#define fi first
#define se second
#define wez(n) int (n); scanf("%d",&(n));
#define wez2(n,m) int (n),(m); scanf("%d %d",&(n),&(m));
#define wez3(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k));
inline void pisz(int n) { printf("%d\n",n); }
template<typename T,typename TT> ostream& operator<<(ostream &s,pair<T,TT> t) {return s<<"("<<t.first<<","<<t.second<<")";}
template<typename T> ostream& operator<<(ostream &s,vector<T> t){FOR(i,SZ(t))s<<t[i]<<" ";return s; }
#define DBG(vari) cout<<"["<<__LINE__<<"] "<<#vari<<" = "<<(vari)<<endl;
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (__typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define TESTS wez(testow)while(testow--)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));
#define IOS ios_base::sync_with_stdio(0);

#define ull unsigned ll
// dla n < 2^32: inline ull mul(ull a, ull b, ull mod) { return (a*b) % mod; }
const int _k = 25; const ull _mask = (1<<_k)-1;
ull mul (ull a, ull b, ull mod) { // zał: b, mod < 2^(64-_k)
    ull result = 0;
    while (a) {
        ull temp = (b * (a & _mask)) % mod;
        result = (result + temp) % mod;
        a >>= _k;
        b = (b << _k) % mod;
    }
    return result;
}

ull pow (ull a, ull w, ull mod) {
    ull res = 1;
    while (w){
        if (w&1) res = mul(res, a, mod);
        a = mul(a, a, mod);
        w /= 2;
    }
    return res;
}

bool primetest (ull n, int a) {
    if (a > n-1) return 1;
    ull d = n-1;
    int s = 0;
    while (!(d&1)) {
        d /= 2;
        s++;
    }
    ull x = pow(a, d, n);
    if (x == 1 || x == n-1) return 1;
    FOR(i,s-1){
        x = mul(x, x, n);
        if (x == 1) return 0;
        if (x == n-1) return 1;
    }
    return 0;
}

bool isPrime(ull n) {
    if (n < 4) return n > 1;
    bool pr = n%2;
    // czesc galezi ifow ponizej czesto mozna pominac (np. jak mamy tylko n < 2^32)
    if (n < (1LL << 32)) {
       for (int a : {2,7,61}) pr = pr && primetest(n,a);
    } else if (n < (1LL << 48)) {
       for (int a : {2,3,5,7,11,13,17}) pr = pr && primetest(n,a);
    } else {
       for (int a : {2,325,9375,28178,450775,9780504,1795265022}) pr = pr && primetest(n,a);
    }
    return pr;
}
/* Test mozna przyspieszyc, sprawdzajac najpierw podzielnosc przez
 * pierwsze kilkanascie liczb pierwszych. */


// dziala w czasie O(n^0.25)
// zostawia wynik w mapie roz
// przed uzyciem zrobic roz.clear()

map<ull,int> roz; // rozklad: {<liczba pierwsza, krotnosc>}
ull find_factor(ull z) {
    if (!(z&1)) return 2;
    ull c = rand() % z, x = 2, y = 2, d = 1;
    while (d == 1) {
        ull tp = (mul(y,y,z) + c) % z;
        y = (mul(tp,tp,z) + c) % z;
        x = (mul(x,x,z) + c) % z;
        d = __gcd(x>y ? x-y : y-x, z);
    }
    return d;
}
void rhofact(ull z) {
    if (z==1) return;
    if (isPrime(z)) { roz[z]++; return; }
    while(1) {
        ull f = find_factor(z);
        if (f != z) {
            rhofact(f);
            rhofact(z/f);
            break;
        }
    }
}

int main () {
   IOS
   int n;
   cin >> n;
   bool has1 = 0;
   map<ll,int> m;
   map<ll,ll> para;
   int res = 0;
   FOR(i,n) {
      ll x;
      cin >> x;
      roz.clear();
      rhofact(x);
      x = 1;
      ll p = 1;
      double dblP = 1;
      for (auto it : roz) {
         int krot = it.se % 3;
         if (krot) { // 1 or 2
            FOR(u,krot) {
               x *= it.fi;
            }
            FOR(u,3-krot) {
               p *= it.fi;
               dblP *= it.fi;
            }
         }
      }
      if (x == 1) {
         has1 = 1;
      } else {
         if (dblP > 1001001001001001LL) {
            ++res;
         } else {
            m[x]++;
            m[p];
            para[x] = p;
            para[p] = x;
         }
      }
      
   }
   res += has1;
   for (auto it : m) {
      ll x = it.fi;
      ll p = para[x];
      if (x < p) {
         res += max(it.se, m[p]);
      }
   }
   cout << res;
}

Submission Info

Judge Result