【数论】AGC003 Anticube

分析：

有点套路的数学题。

很显然，如果把每个数质因数分解，那么每个质因数的次数对3取模，归为一类，然后对每一类而言，考虑与其矛盾的类，取max即可。

重点就在于如何质因数分解。

很显然，如果要取模，则先保证质数的三次方在$10^{10}$以内，那么质数的范围就大大缩小，到了$[2,3?10^3]$左右。这个范围内质数的个数就更少了，大约$340$多个，那么可以直接把这一类质数筛掉，然后剩余的数只有三种可能：$a_i=p$或$a_i=p^2或a_i=p?q(p,q为互不相同的质数)$，本质上1和3情况是一致的，所以只需要开个根号判断一下是不是2情况即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define SF scanf
#define PF printf
#define MAXN 100010
#define MAXP 2300
using namespace std;
typedef long long ll;
int primes[MAXN],cnt;
int isprime[MAXP+100];
ll a[MAXN],les[MAXN],les1[MAXN];
map<ll,int> mp,st;
void prepare(){
    for(int i=2;i<=MAXP;i++){
    if(isprime[i]==0)primes[++cnt]=i;for(int j=1;i*primes[j]<=MAXP;j++){
    isprime[i*primes[j]]=1;if(i%primes[j]==0)break;	}}
}
int main(){
    prepare();//PF("%d",cnt);int n;SF("%d",&n);for(int i=1;i<=n;i++){
    SF("%lld",&a[i]);les1[i]=les[i]=a[i];}for(int i=1;i<=cnt;i++){
    ll p=primes[i];ll p2=p*p;ll p3=p*p*p;for(int j=1;j<=n;j++)if(a[j]%p==0){
    while(a[j]%p3==0){
    a[j]/=p3;les1[j]/=p3;les[j]/=p3;}if(les1[j]%p2==0){
    les1[j]/=p;les[j]/=p;}if(les[j]%p==0)les[j]/=p;}}for(int i=1;i<=n;i++){
    if(les[i]==1){
    les[i]=les1[i];continue;}ll x=(long long)sqrt(les[i]);if(x*x==les[i])les[i]=les1[i]/x;elseles[i]=les1[i];	}	int ans=0;for(int i=1;i<=n;i++){
    if(a[i]==1){
    ans=1;continue;}mp[a[i]]++;st[a[i]]=les[i];}map<ll,int>::iterator it=mp.begin();for(;it!=mp.end();it++){
    ll x=it->first;int sum=it->second;ll y=st[x];ll xi=y*y/x*y;if(mp.count(xi)==0)ans+=sum;else{
    if(xi>x)ans+=max(sum,mp[xi]);	}}PF("%d",ans);
}