预处理
WA了N次。。。。。。。。
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 const int maxn = 1000005; 6 const int maxm = 1005; 7 int s[ maxn ],vis[ maxm ]; 8 int main(){ 9 memset( s,0,sizeof(s) ); 10 memset( vis,0,sizeof(vis) ); 11 int cnt=0; 12 int i,j; 13 int max=-1; 14 for( i=1;i<maxn/2;i++ ){ 15 for( j=i*2;j<maxn;j+=i ){ 16 if( j%i==0 ) s[ j ]+=i; 17 } 18 } 19 for( i=2;i<maxn;i++ ){ 20 if( s[i]<=1000) 21 vis[ s[ i ] ]++; 22 //if( s[i]>max ) max=s[i]; 23 } 24 //printf("max:%d\n",max); 25 int T; 26 scanf("%d",&T); 27 while( T-- ){ 28 int n; 29 scanf("%d",&n); 30 if( vis[ n ]==0 ) printf("yes\n"); 31 else printf("no\n"); 32 } 33 return 0; 34 }