D - ABC Conjecture Gym - 102798D

題意：

規(guī)定rad(n)=n的所有質(zhì)因子的乘積
給你一個c，問能否構(gòu)造a和b使得a+b=c且rad(abc)<c

題解：

先說結(jié)論，如果c可以拆分出兩個一樣的質(zhì)因子，則能構(gòu)造a和b
即 n=p1^a1 * p2^a2 . . .*pn^an,
a1到an有一個>=2即可
為什么？
首先如果a1到an都是1，那rad?=c,那么rad(abc)不可能小于c
如果a1到an存在一個>=2，怎么能夠說明rad(abc)<c?看下圖

看本題，1<=c<=1e18
線性篩可以曬出1e7以內(nèi)，那么也就是可以解決[1,1e14]以內(nèi)的c，那1e14到1e18之間如何解決？
我們想c = P ⁿ *x,n>=2
P為[1e14,1e18]以內(nèi)的素數(shù),那n只能是2，不然c就超范圍了，而x最大也才到1e4，所有我們可以將c先除x，然后看（int）sqrt(c/x) 的平方是否等于c/x，相當于反向驗證了是否存在P
詳細看代碼：

代碼:

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e7; int prime[maxn+1]; bool vis[maxn]; void getprime() {vis[1]=1;for(int i=2;i<=maxn;i++){if(!vis[i])prime[++prime[0]]=i;for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){vis[prime[j]*i]=1;if(i%prime[j]==0)break;}} } int main() {getprime();int t;cin>>t;while(t--){ll x;cin>>x;bool f=0;for(int j=1;j<=prime[0];j++){if(x%(prime[j]*prime[j])==0){f=1;break;}else if(x==1){f=0;break;}else if(x%prime[j]==0)x/=prime[j];}if(f==1)cout<<"yes"<<endl;else if(x==1)cout<<"no"<<endl;else {ll w=sqrt(1.0*x);if(w*w==x)cout<<"yes"<<endl;else cout<<"no"<<endl;}}return 0; } /* 54 1000000007 */

總結(jié)

以上是生活随笔為你收集整理的D - ABC Conjecture Gym - 102798D的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。