题解
2024-09-30 21:23:14
发布于:上海
35阅读
0回复
0点赞
思路:
下表是一个很简单的模拟得到的结果。
n | 结果 |
---|---|
1 | × |
2 | × |
3 | × |
4=22 | × |
5 | × |
6=2×3 | (1,2,3) |
7 | × |
8=23 | × |
9=32 | × |
10=2×5 | (1,1,1,2,5) |
……
上述过程由简单模拟得到。接下来根据上面的表格或许可以更好地理解:
如果对于一个数n而言,若它只有一种大于1的质因数x,又想保证满足第二个式子,那么a1必然为n或n的因数,又由于满足a1+a2+...+ak=n且lcm(a1,a2,...,ak)=n,则对于任何1<=i<=k而言,ai为n的因数,又倘若只有一种大于1的因数x,则ai必为x的正整数次数幂,结合lcm的特性知这里只会选择max(a1,a2,...,ak)作为lcm的结果,故若想要第二个式子成立,必然需要让a1=n,针对1<j<=k,aj=1。又因为a1+a2+...+ak=n,故知k=1,与题目中要求k>2矛盾,因此,n至少有2种大于1的质因数。重复上述过程,易知如n=10这种含有2种及以上的质因数的数是青蛙数。
代码:
#include<iostream>
#define int long long
using namespace std;
int t,n,c;
signed main(){
cin>>t;
while(t--){
c=0;
cin>>n;
if(n==1)cout<<"No"<<endl;
else{
c+=n%2==0;
while(n%2==0)n/=2;
for(int i=3;i*i<=n;i+=2){
c+=n%i==0;
while(n%i==0)n/=i;
}
c+=n>1;
cout<<(c>1?"Yes":"No")<<endl;
}
}
return 0;
}
这里空空如也
有帮助,赞一个