Problem Statement
Snuke got positive integers $s_1,...,s_N$ from his mother, as a birthday present. There may be duplicate elements.
He will circle some of these $N$ integers. Since he dislikes cubic numbers, he wants to ensure that if both $s_i$ and $s_j (i ≠ j)$ are circled, the product $s_is_j$ is not cubic. For example, when $s_1=1,s_2=1,s_3=2,s_4=4$, it is not possible to circle both $s_1$ and $s_2$ at the same time. It is not possible to circle both $s_3$ and $s_4$ at the same time, either.
Find the maximum number of integers that Snuke can circle.
Constraints
- $1 ≦ N ≦ 10^5$
- $1 ≦ s_i ≦ 10^{10}$
- All input values are integers.
首先 Pollard-Pho 分解质因数(bushi
然后考虑把 \(x\) 每一个因数的指数 \(\bmod 3\) 后出来一个数 \(f(x)\)。那么在这个问题中，若 \(f(x)=f(y)\) ，那么 \(x\) 和 \(y\) 本质是相同的，看做一个等价类。
同时可以发现，把所有指数给取反后，出来一个 \(g(x)\)，那么 \(g(x)\) 代表的等价类和 \(f(x)\) 中的数不能同时出现。
这样就很好统计了。
然后你真的想用 Pollar-Pho 吗？
对于 \(x\) 的某一个超过 \(\sqrt[3]{n}\) 质因数，他的指数不会超过 \(3\)，所以容易算出 \(f(x)\)
在计算 \(g(x)\) 的时候，把所有在 \(\sqrt[3]{n}\) 之内的因数筛完之后，假设出来是 \(d\)，那么如果 \(d=x^2\)，\(g(x)\) 乘上 \(\sqrt{d}\)，否则如果 \(d\le 1000000\)，\(g(x)\) 乘上 \(d^2\)，否则 \(g(x)\) 一定超过 \(10^{12}\)，不用管。
using namespace std;
typedef long long LL;
const int N=1e5+5;
int n,ans;
LL s;
LL read()
{
LL s=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s;
}
map<LL,LL>to,mp;
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
s=read();
LL v=1,g=1;
for(int j=2;j<=2200;j++)
{
if(s%j==0)
{
int c=0;
while(s%j==0)
s/=j,++c;
c%=3;
if(c==1)
v*=1LL*j*j,g*=j;
else if(c)
v*=j,g*=1LL*j*j;
}
}
g*=s;
mp[g]++;
int k=sqrt(s);
if(1LL*k*k==s)
v*=k,to[g]=v;
else if(s<=1000000)
v*=1LL*s*s,to[g]=v;
}
for(map<LL,LL>::iterator it=mp.begin();it!=mp.end();it++)
{
LL x=(*it).first;
if(x==1)
ans++;
else
ans+=max(mp[x],to.find(x)!=to.end()&&mp.find(to[x])!=mp.end()? mp[to[x]]:0);
mp[x]=mp[to[x]]=0;
}
printf("%d",ans);
}