Instantly share code, notes, and snippets.

ctylim/AGC003D.cpp Created Aug 25, 2016

What would you like to do?
AGC 003 D
 #include #include #include #include #include #include #include #include #include #include #include #include #include #define repd(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repd(i,0,n) #define all(x) (x).begin(),(x).end() #define mod 1000000007 #define inf 2000000007 #define mp make_pair #define pb push_back typedef long long ll; using namespace std; template inline void output(T a, int p) { if(p) cout << fixed << setprecision(p) << a << "\n"; else cout << a << "\n"; } // end of template vector primes; void make_primes(){ primes.pb(2); for(ll n = 3; n <= 2200; n++){ // 2200^3 > 10^10 bool isPrime = true; for(ll i = 0; primes[i] * primes[i] <= n && i < primes.size(); i++){ if(n % primes[i] == 0) { isPrime = false; break; } } if(isPrime) primes.pb(n); } } int main() { cin.tie(0); ios::sync_with_stdio(0); // source code make_primes(); int N; cin >> N; vector A(N); rep(i, N) { cin >> A[i]; for(ll prime: primes){ while(1){ if(A[i] % (prime * prime * prime) == 0){ A[i] /= prime * prime * prime; } else{ break; } } } } sort(all(A)); vector> C; map M; ll num = -1; rep(i, N){ if (num == A[i]){ C.back().second++; } else{ C.pb(mp(A[i], 1)); M[A[i]] = (int)C.size(); // index + 1 } num = A[i]; } vector vis(C.size(), 0); // チェックしたか int ret = 0; // a*b^2 and a^2*b rep(i, C.size()){ if(vis[i] > 0 || C[i].first == 1) continue; ll a = C[i].first; ll b = 1; for(ll prime: primes){ if(a % (prime * prime) == 0){ a /= (prime * prime); b *= prime; } } if(M[a * a * b] > 0){ ret += max(C[i].second, C[M[a * a * b] - 1].second); vis[i] = 1, vis[M[a * a * b] - 1] = 1; } else{ ret += C[i].second; vis[i] = 1; } } // a and a^2 rep(i, C.size()){ if(C[i].first > 100000) break; // (10^5)^2=10^10 if(vis[i] > 0 || C[i].first == 1) continue; ll a = C[i].first; ll b = a * a; if(M[b] > 0){ ret += max(C[i].second, C[M[b] - 1].second); vis[i] = 1, vis[M[b] - 1] = 1; } else{ ret += C[i].second; vis[i] = 1; } } // 1だけ特別に処理 rep(i, C.size()){ if(vis[i] == 0){ if(C[i].first == 1) ret++; else ret += C[i].second; } } output(ret, 0); return 0; }