自助建站网站系统,移动营销,深圳建设工程交易网站,网页大图素材D - ABC Conjecture Gym - 102798D
题意#xff1a;
规定rad(n)n的所有质因子的乘积 给你一个c#xff0c;问能否构造a和b使得abc且rad(abc)c
题解#xff1a;
先说结论#xff0c;如果c可以拆分出两个一样的质因子#xff0c;则能构造a和b 即 np1a1 * p2a2 . . .…D - ABC Conjecture Gym - 102798D
题意
规定rad(n)n的所有质因子的乘积 给你一个c问能否构造a和b使得abc且rad(abc)c
题解
先说结论如果c可以拆分出两个一样的质因子则能构造a和b 即 np1a1 * p2a2 . . .*pnan, a1到an有一个2即可 为什么 首先如果a1到an都是1那rad©c,那么rad(abc)不可能小于c 如果a1到an存在一个2怎么能够说明rad(abc)c?看下图 看本题1c1e18 线性筛可以晒出1e7以内那么也就是可以解决[1,1e14]以内的c那1e14到1e18之间如何解决 我们想c P n *x,n2 P为[1e14,1e18]以内的素数,那n只能是2不然c就超范围了而x最大也才到1e4所有我们可以将c先除x然后看intsqrt(c/x) 的平方是否等于c/x相当于反向验证了是否存在P 详细看代码
代码:
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn1e7;
int prime[maxn1];
bool vis[maxn];
void getprime()
{vis[1]1;for(int i2;imaxn;i){if(!vis[i])prime[prime[0]]i;for(int j1;jprime[0]prime[j]maxn/i;j){vis[prime[j]*i]1;if(i%prime[j]0)break;}}
}
int main()
{getprime();int t;cint;while(t--){ll x;cinx;bool f0;for(int j1;jprime[0];j){if(x%(prime[j]*prime[j])0){f1;break;}else if(x1){f0;break;}else if(x%prime[j]0)x/prime[j];}if(f1)coutyesendl;else if(x1)coutnoendl;else {ll wsqrt(1.0*x);if(w*wx)coutyesendl;else coutnoendl;}}return 0;
}
/*
54
1000000007
*/
