POJ2635 The Embarrassed Cryptographer 万进制+素数筛选

　　重点在万进制优化，主要是mod操作少了很多。
 1 //STATUS:C++_AC_938MS_4432KB
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<iostream>
 7 #include<string>
 8 #include<algorithm>
 9 #include<vector>
10 #include<queue>
11 #include<stack>
12 using namespace std;
13 #define LL __int64
14 #define pii pair<int,int>
15 #define Max(a,b) ((a)>(b)?(a):(b))
16 #define Min(a,b) ((a)<(b)?(a):(b))
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define lson l,mid,rt<<1
19 #define rson mid+1,r,rt<<1|1
20 const int N=110,M=1000000,INF=0x3f3f3f3f,MOD=1999997;
21 const LL LLNF=0x3f3f3f3f3f3f3f3fLL;
22 
23 char s[N];
24 int num[N],pri[M+10],isp[M+10];
25 int p,k,hav;
26 
27 inline int yu(int m)
28 {
29     int i;
30     LL t;
31     for(i=k-1,t=0;i>=0;i--){
32         t=num[i]+t*1000000;
33         t%=m;
34     }
35     return t;
36 }
37 
38 int main()
39 {
40  //   freopen("in.txt","r",stdin);
41     int i,j,len,ok;
42     len=(int)sqrt(M*1.0);
43     for(i=2;i<=len;i++)
44         if(!isp[i])
45             for(j=i+i;j<=M;j+=i)isp[j]=1;
46     for(i=2,hav=0;i<=M;i++)
47         if(!isp[i])pri[hav++]=i;
48     while(~scanf("%s%d",s,&p) && p)
49     {
50         ok=k=0;
51         len=strlen(s);
52         for(i=len-1;i>=0;k++)
53             for(num[k]=0,j=1;j<1000000 && i>=0;j*=10,i--)
54                 num[k]+=(s[i]-'0')*j;
55         for(i=0;pri[i]<p && i<hav;i++)
56             if(!yu(pri[i])){ok=1;break;};
57 
58         if(ok)printf("BAD %d\n",pri[i]);
59         else printf("GOOD\n");
60     }
61     return 0;
62 }