Atcoder 2004:Anticube(素因数分解、思考)
2596 ワード
Snuke got positive integers s1,…,sN 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 si and sj(i≠j) are circled, the product sisj is not cubic. For example, when s1=1,s2=1,s3=2,s4=4, it is not possible to circle both s1 and s2 at the same time. It is not possible to circle both s3 and s4 at the same time, either.
Find the maximum number of integers that Snuke can circle.
Constraints 1≦N≦105 1≦si≦1010 All input values are integers. Input The input is given from Standard Input in the following format:
N s1 : sN Output Print the maximum number of integers that Snuke can circle.
Sample Input 1 8 1 2 3 4 5 6 7 8 Sample Output 1 6 Snuke can circle 1,2,3,5,6,7.
Sample Input 2 6 2 4 4 8 16 32 64 Sample Output 2 3 Sample Input 3 1011000000007 10000000 10000000 0009 9999999999 Sample Output 3 9題意:長さnの数列を与え、中にいくつかの数を見つけて、任意の2つの数ai、ajが乗算して立方数ではないようにします.题解:この问题は2つの数を乗じて立方数ではないので、私达は质因数で分解して、质因数を分解した后にすべての质因数を模3して、それからそれとその补数(例えば3の1回の方の补数は3の2回の方で、5の2回の方の补数は5の1回の方)を得ることができて、それとその补数は1対1で対応して、だから私达はそれとその补数の间で出现回数を取って最も多く得て、しかし、この問題は100000個の数に対して質因子を求めるといくつかのケースがタイムアウトします.この問題は立方晶であるため、sqrt 3(1 e 10)個の数を判断する質因子しか表を打っていません.sqrt 3(1 e 10)より大きい場合は、完全な平方数ではないか、完全な平方数ではないかを判断するしかありません.質因子はsqrt 3(1 e 10)より大きいので、だからその補数は1 e 10より大きいに違いないので、勝手に選ぶことができます.ACコード
He will circle some of these N integers. Since he dislikes cubic numbers, he wants to ensure that if both si and sj(i≠j) are circled, the product sisj is not cubic. For example, when s1=1,s2=1,s3=2,s4=4, it is not possible to circle both s1 and s2 at the same time. It is not possible to circle both s3 and s4 at the same time, either.
Find the maximum number of integers that Snuke can circle.
Constraints 1≦N≦105 1≦si≦1010 All input values are integers. Input The input is given from Standard Input in the following format:
N s1 : sN Output Print the maximum number of integers that Snuke can circle.
Sample Input 1 8 1 2 3 4 5 6 7 8 Sample Output 1 6 Snuke can circle 1,2,3,5,6,7.
Sample Input 2 6 2 4 4 8 16 32 64 Sample Output 2 3 Sample Input 3 1011000000007 10000000 10000000 0009 9999999999 Sample Output 3 9題意:長さnの数列を与え、中にいくつかの数を見つけて、任意の2つの数ai、ajが乗算して立方数ではないようにします.题解:この问题は2つの数を乗じて立方数ではないので、私达は质因数で分解して、质因数を分解した后にすべての质因数を模3して、それからそれとその补数(例えば3の1回の方の补数は3の2回の方で、5の2回の方の补数は5の1回の方)を得ることができて、それとその补数は1対1で対応して、だから私达はそれとその补数の间で出现回数を取って最も多く得て、しかし、この問題は100000個の数に対して質因子を求めるといくつかのケースがタイムアウトします.この問題は立方晶であるため、sqrt 3(1 e 10)個の数を判断する質因子しか表を打っていません.sqrt 3(1 e 10)より大きい場合は、完全な平方数ではないか、完全な平方数ではないかを判断するしかありません.質因子はsqrt 3(1 e 10)より大きいので、だからその補数は1 e 10より大きいに違いないので、勝手に選ぶことができます.ACコード
#include
#define ll long long
using namespace std;
ll p[2200],a[100005],k[100005];
int cnt=0;
mapx;
mapvis;
ll M(ll t,ll h)
{
ll ans1=1,ans2=1;
for(int i=0;i1e10) ans2=0;
ans2*=p[i];
}
else ans1*=p[i]*p[i],ans2*=p[i];
if(ans2>1e10) ans2=0;
}
ans1*=t;
ll w=(ll)sqrt(t);
if(w*w==t)
ans2*=w;
else
{
ans2*=t;
if(ans2>1e10) ans2=0;
ans2*=t;
}
if(ans2>1e10) ans2=0;
x[ans1]++;
k[h]=ans2;
return ans1;
}
int main()
{
for(int i=2;i<=2200;i++)
{
bool flag=true;
for(int j=2;j*j<=i;j++)
if(i%j==0) {flag=false;break;}
if(flag) p[cnt++]=i;
}
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
ll m;
scanf("%lld",&m);
a[i]=M(m,i);
}
int ans=0;
vis[1]=true;
for(int i=1;i<=n;i++)
if(!vis[a[i]]) ans+=max(x[a[i]],x[k[i]]),vis[a[i]]=vis[k[i]]=true;
if(x[1]>=1) ans++;
printf("%d
",ans);
}