两题水题：
1.如果一个数能被分解为两个素数的乘积，则称为Semi-Prime，给你一个数，让你判断是不是Semi-Prime数。
2.定义F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2) 让你判断第n项是否能被3整除。
1.ZOJ 2723 Semi-Prime
http://acm./onlinejudge/showProblem.do?problemId=1723
打表即可。
#include<cstdio>const int MAXN=500000+10;bool prime[MAXN]={0};int num[MAXN],len;int main(){for(int i=2;i*i<MAXN;i++)if(!prime[i])for(int j=i;j*i<MAXN;j++)prime[i*j]=1;for(int i=2;i<MAXN;i++)if(!prime[i])num[len++]=i;int n;while(~scanf("%d",&n)){int cnt=0,cur=0;while(n!=1){while( n % num[cur]==0){cnt++;n/=num[cur];}cur++;if(cur >= len /*|| cnt >2*/ )break;}if(cnt==2)puts("Yes");elseputs("No");}return 0;}
2.ZOJ 2060 Fibonacci Again
http://acm./onlinejudge/showProblem.do?problemId=1060
不mod 3 会溢出。
方法1：直接打表
#include<cstdio>const int MAXN=1000000+2;int f[MAXN];int main(){f[0]=7%3;f[1]=11%3;for(int i=2;i<MAXN;i++)f[i]=(f[i-1]%3+f[i-2]%3)%3;int n;while(~scanf("%d",&n)){if(f[n] ==0)puts("yes");elseputs("no");}return 0;}
方法2：
看上面的打表，可发现每8项一循环。
#include<cstdio>const int MAXN=8;int f[MAXN];int main(){f[0]=7%3;f[1]=11%3;for(int i=2;i<8;i++)f[i]=(f[i-1]%3+f[i-2]%3)%3;int n;while(~scanf("%d",&n)){if(f[n % 8] ==0)puts("yes");elseputs("no");}return 0;}
