深度解构_ioncube解密

首先，这道题我们一看数据10^18，很大，要1000ms出结果简直是天方夜谭，当然我们有神器。

在数论中，我们都知道任何一个数都可以表示为若干个素数的乘积，当然素数可以相同，这就是唯一分解定理。

然后知道这个之后就必然有：

然后本题我们可以这样考虑：如果n的最小的素因子都超过10^6，那么我们说n最多只能分解成两个素因子的乘积，因为如果可以分解成3个，n就超过了

10^18了，所以现在解法很明显了。

我们可以这样，先筛选出1到10^6内的素数，然后枚举某一个素因子能否被整除两次，如果能被整除两次，那么答案就直接出来了，但是如果不能被整除两

次，那么就只能是0次或者一次，对于0次我们可以不用管，而对于1次的，每次就把这个素因子除掉，然后继续验证剩余的，直到1到10^6以内的素因子都

验证完毕，如果都不存在，那么如果此时的n要么大于10^6，要么等于1，当然 ，如果等于1，那么答案就已经很明了，如果大于10^6，这时，表明n存在大

于10^6的素因子，而这个因子的次方最多为2，所以现在只需要再通过开平方验证即可，然后本题就这样完美解决。

#include <stdio.h> #include <string.h> #include <math.h> #define LL long long const LL N = ; LL p[N]; bool prime[N]; LL n,k=0; void isprime() { LL i,j; memset(prime,true,sizeof(prime)); for(i=2;i<N;i++) { if(prime[i]) { p[k++]=i; for(j=i+i;j<N;j+=i) { prime[j]=false; } } } } bool Test() { int i; for(i=0;i<k;i++) { if(n%p[i]==0) { n/=p[i]; if(n%p[i]==0) return false; } } return true; } int main() { LL t=1,T; isprime(); bool flag; scanf("%I64d",&T); while(T--) { flag=false; scanf("%I64d",&n); printf("Case %d: ",t++); if(!Test()) flag=true; if(n>) { LL temp=(LL)sqrt((double)n); if(temp*temp==n) flag=true; } if(flag) puts("No"); else puts("Yes"); } return 0; }