不可摸数是数论中的一个难题，在20世纪70年代的时候被提出。每一个数都有一个积性函数与其对应，所谓积性函数就是这个数的所有因子之和记做u(x);而这个数的所有真因子之和记做s(x);那么有这样的式子：x=u(x)-s(x);而u(x)是很好求出的，因为我们知道任何一个数都可以表示成若干个质数成绩的形式。那么u(x)=u(p^m*q^n)=(p^0+p^1+…p^m)*(q^0+q^1+…q^n);所以s(x)也很好求出的了；对于这个题有两个引理和公认：1.
若x为大于2的偶数，那么s(x)>x/2;2.
若x是一个正奇数，而s(x)是偶数，那么x必然是一个平方数。3.
只有一个不可摸数是奇数，那是5第一个很好理解，第二个还没看懂证明，可以先使用。所以我们做这个题就可以只考虑偶数的情况了，然后按照两个引理可以很快完成题目；#include#include#includebool hash[1001];int prime[170];bool prim(int n){//质数判定
int i,s=(int)sqrt(n+.0);
for(i=2;i0&&n%prime==0){
t+=j;
j*=prime;
n/=prime;
}
t+=j;
sum*=t;
}
if(n==0) break;
}
return sum-k;}int main(){
int i,j;
for(i=2,j=0;i<=1000;i++)
if(prim(i))
prime[j++]=i;
prime[j]=0;
for(i=2;i<=2000;i+=2){//用到引理1
j=getv(i);
if(j<=1000)
hash[j]=1;
}
for(i=3;i<=1000;i+=2){//用到引理2
j=getv(i*i);
if(j<=1000)
hash[j]=1;
}
int T,N;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
if(N==5) printf("yes\n");
else if(hash[N]||N%2==1) printf("no\n");//是奇数或者虽是偶数，但是有别的s(x)等于它
else printf("yes\n");
}
return 0;} |
