首页 > 代码库 > poj2635（The Embarrassed Cryptographer）
poj2635（The Embarrassed Cryptographer）
题目地址：The Embarrassed Cryptographer
题目大意：
给定一个大数K，K是两个大素数的乘积的值。再给定一个int内的数L问这两个大素数中最小的一个是否小于L，如果小于则输出这个素数。
解题思路：
高精度求模+同余模定理
同余模定理：
例如要验证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进制下的做法，因为K很大，如果暴力从1枚举到L（L<=10^6），时间复杂度大约为10^8。
所以需要将K数组进行转化为千位进制的数组Kt ，时间复杂度大约是10^6。
千进制的性质与十进制相似。
例如，把K=1234567890转成千进制，就变成了：Kt=[ 1][234][567][890]。
为了方便处理，我的程序是按“局部有序，全局倒序”模式存放Kt
即Kt=[890][567][234][1 ] (一个中括号代表一个数组元素)
转：http://blog.csdn.net/lyy289065406/article/details/6648530
代码：
1 #include <iostream> 2 #include <cmath> 3 #include <algorithm> 4 #include <cstdio> 5 #include <cstdlib> 6 #include <cstring> 7 using namespace std; 8 const int M=1000100; 9 int p[M],vis[M];10 int prime()11 {12 int i,j;13 int d=0;14 memset(vis,1,sizeof(vis));15 vis[0]=0;16 vis[1]=0;17 vis[2]=1;18 for(i=2; i<=sqrt(M); i++)19 {20 if (vis[i])21 for(j=i+i; j<=M; j+=i)22 {23 vis[j]=0;24 }25 }26 for(i=0; i<=M; i++)27 if(vis[i])28 p[d++]=i;29 }30 int main()31 {32 int l;33 char k[105];34 int kk[100];35 prime();36 while(scanf("%s%d",&k,&l)&&l)37 {38 int i,j;39 int len=strlen(k);40 int d=0,cnt=0,t,tt,ttt;41 for(i=len-1; i>=0; d++)42 {43 t=k[i]-‘0‘;44 t=t;45 i--;46 kk[d]=t;47 if (i<0)48 break;49 tt=k[i]-‘0‘;50 tt=tt*10+t;51 i--;52 kk[d]=tt;53 if (i<0)54 break;55 ttt=k[i]-‘0‘;56 ttt=ttt*100+tt;57 i--;58 kk[d]=ttt;59 if (i<0)60 break;61 }62 int ce,flag=0;63 while(p[cnt]<l)64 {65 for(ce=0,i=d; i>=0; i--)66 {67 ce=(ce*1000+kk[i])%p[cnt];68 }69 if (ce==0)70 {71 flag=1;72 break;73 }74 cnt++;75 }76 if (flag)77 printf("BAD %d\n",p[cnt]);78 else79 printf("GOOD\n");80 memset(k,0,sizeof(k));81 memset(kk,0,sizeof(kk));82 }83 return 0;84 }
poj2635（The Embarrassed Cryptographer）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。