Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
AGC 003 D
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#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 <typename T>
inline void output(T a, int p) {
if(p) cout << fixed << setprecision(p) << a << "\n";
else cout << a << "\n";
}
// end of template
vector<ll> 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<ll> 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<pair<ll, int>> C;
map<ll, int> 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<int> 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment