转载请注明出处：優YoU
大致题意：
给定一个大数K，K是两个大素数的乘积的值。
再给定一个int内的数L
问这两个大素数中最小的一个是否小于L，如果小于则输出这个素数。
解题思路：
首先对题目的插图表示无语。。。
高精度求模+同余模定理
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就可以了
Source修正：
1 //Memory Time 2 //624K 1235MS 3 4 #include5 #include 6 using namespace std; 7 8 const int Range=1000100; //打表不能只打到100W，素数表中最大的素数必须大于10^6 9 10 int Kt[10000]; //千进制的K 11 int L; 12 int prime[Range+1]; 13 14 /*素数组打表*/ 15 void PrimeTable(void) 16 { 17 int pNum=0; 18 prime[pNum++]=2; 19 20 for(int i=3;i<=Range;i+=2) //奇偶法 21 { 22 bool flag=true; 23 for(int j=0;prime[j]*prime[j]<=i;j++) //根号法+递归法 24 if(!(i%prime[j])) 25 { 26 flag=false; 27 break; 28 } 29 if(flag) 30 prime[pNum++]=i; 31 } 32 return; 33 } 34 35 /*高精度K对p求模，因数检查(整除)*/ 36 bool mod(const int* K,const int p,const int len) 37 { 38 int sq=0; 39 for(int i=len-1;i>=0;i--) //千进制K是逆序存放 40 sq=(sq*1000+K[i])%p; //同余模定理 41 42 if(!sq) //K被整除 43 return false; 44 return true; 45 } 46 47 int main(void) 48 { 49 PrimeTable(); 50 51 char K[10000]; 52 while(cin>>K>>L && L) 53 { 54 memset(Kt,0,sizeof(Kt)); 55 int lenK=strlen(K); 56 for(int i=0;i
Sample Input 143 10 143 20 667 20 667 30 2573 30 2573 40 4 2 6 3 6 3 15 3 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689 2 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689 3 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689 999981 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689 999982 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689 999983 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689 999984 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689 999985 9936798836621706335903766366605021199756127575438907144689843371764114998372849970522970722679648297 1000000 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999924165887 1000000 9999999999999999997709341477512928270733515750111494296807693217401592660013176273247584305454312971 1000000 9999999999988881245087379264540384030358544520360773252628174690915590034078934845096473005364364269 1000000 9999999999999999999999999999999999999999999999999999999999999999999997947710886296926452585995644787 1000000 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998743929569 1000000 9999999999999999999999999999999999999999999999999999999999999999999999996406876316697599258447653751 1000000 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995271511 1000000 9999664515006205757944572422495695942633452678405393581216966782816097132509526872495414067984894021 1000000 0 0
Sample Output GOOD BAD 11 GOOD BAD 23 GOOD BAD 31 GOOD BAD 2 BAD 2 GOOD GOOD GOOD GOOD GOOD GOOD BAD 999983 BAD 999983 BAD 587 BAD 100043 GOOD GOOD GOOD GOOD GOOD BAD 16603 BAD 9103