高精度求模+同余模定理
1、 Char格式读入K。把K转成千进制Kt，同时变为int型。
把数字往大进制转换能够加快运算效率。若用十进制则耗费很多时间，会TLE。
千进制的性质与十进制相似。
例如，把K=1234567890转成千进制，就变成了：Kt=[ 1][234][567][890]。
为了方便处理，我的程序是按“局部有序，全局倒序”模式存放Kt
即Kt=[890][567][234][1 ] (一个中括号代表一个数组元素)
2、 素数打表，把10^6内的素数全部预打表，在求模时则枚举到小于L为止。
注意打表不能只打到100W，要保证素数表中最大的素数必须大于10^6，否则当L=100W且K为GOOD时，会因为数组越界而RE，这是因为越界后prime都是负无穷的数，枚举的while(prime[pMin]<L)循环会陷入死循环
3、 高精度求模。
主要利用Kt数组和同余模定理。
例如要验证123是否被3整除，只需求模124%3
但当123是一个大数时，就不能直接求，只能通过同余模定理对大数“分块”间接求模
具体做法是：
先求1%3 = 1
再求（1*10+2）%3 = 0
再求 （0*10+4）% 3 = 1
那么就间接得到124%3=1，这是显然正确的
而且不难发现， （1*10+2）*10+4 = 124
这是在10进制下的做法，千进制也同理，*10改为*1000就可以了
代码如下：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; int prime[1000010]; bool is_prime[1000010]; int p,l; char a[105]; int kt[100]; void solve( ) { p=0; for(int i=0;i<=1000010;i++) is_prime[i]=true; is_prime[0]=is_prime[1]=false; for(int i=2;i<=1000010;i++){ if(is_prime[i]){ prime[p++]=i; for(int j=2*i;j<=1000010;j+=i) is_prime[j]=false; } } } bool Mod(int p,int len) { int sp=0; for(int i=len-1;i>=0;i--){ sp=(sp*1000+kt[i])%p; } if(!sp) return false; else return true; } int main() { solve(); while(scanf("%s%d",a,&l)){ if(a[0]=='0'&&l==0) break; int len=strlen(a); memset(kt,0,sizeof(kt)); for(int i=0;i<len;i++){ int ii=(len-i+2)/3-1; kt[ii]=kt[ii]*10+a[i]-'0'; } int lenk=(len+2)/3; int flag=true; int kmin=0; while(prime[kmin]<l){ if(!Mod(prime[kmin],lenk)){ flag=false; printf("BAD %d\n",prime[kmin]); break; } kmin++; } if(flag) printf("GOOD\n"); } } 1000进制跑了829ms,100进制跑了1188ms
