首页 > 代码库 > poj2635
poj2635
这道题一看是大数题就知道不会做,就看了一下其他人的解题报告,千篇一律的做法:
首先把大数变成千进制数用整形数组存起来,其实所谓千进制就是每三位数当作一位数处理。
然后从小到大枚举所有小于L的素数,用同余模的各种知识对这个转换后的千进制数进行求余,这个所谓同余模处理,其实就是,设两个正整数a,b,c,有(a+b)%c=(a%c+b)%c,至于证明的话,
我不会。
最后呢,如果余数为0那么输出BAD 比L小的K质因子,如果不是的话,输出GOOD。
附上千进制和万进制的两种做法的代码,其实差不多,如下:
另外从这里http://blog.csdn.net/lyy289065406/article/details/6648530学到了一个判断素数的比较快的方法,就是首先判断这个数是不是偶数,如果不是再枚举小于或等于这个数的平方根的素数,看是不是可以使这个数被整除,如果再不是,那么这个数肯定是素数了。
首先把大数变成千进制数用整形数组存起来,其实所谓千进制就是每三位数当作一位数处理。
然后从小到大枚举所有小于L的素数,用同余模的各种知识对这个转换后的千进制数进行求余,这个所谓同余模处理,其实就是,设两个正整数a,b,c,有(a+b)%c=(a%c+b)%c,至于证明的话,
我不会。
最后呢,如果余数为0那么输出BAD 比L小的K质因子,如果不是的话,输出GOOD。
嗯,这样做就好了。至于为毛是千进制,其实百进制,十进制都可以,用整形数组存起来表示就行了,只是千进制在这里是进行求余过程最优的方法,因为能使求余次数最少。那么为毛不能用万进制,因为会超精的。为毛?因为你想L最大是10的6次方,比它小的素数最大是有6位数的,于是每次对数组里面的每个元素取完一次余,得到的最大余数最大也是有6位数的,于是之后
如果是万进制就要乘以10的4次方加上后面的数组元素,于是最多就会有10位数,int能表示的最大数是2的十次方的样子多一点,当然这里如果用long long的话是可以用万进制的,由于他们都是用千进制,所以,我不仅仅用千进制的方法写了,还用万进制的方法写了。
附上千进制和万进制的两种做法的代码,其实差不多,如下:
#include<iostream> #include<cstring> using namespace std; int prime[1000000],sushu,l,num[110],shumu; char k[110]; bool isprime(int x) { int i; if(x%2==0) return 0; for(i=0;prime[i]*prime[i]<=x;i++) if(x%prime[i]==0) return 0; return 1; } void makeprime() { int i; prime[0]=2; for(sushu=1,i=3;;i++) if(isprime(i)) { prime[sushu++]=i; if(i>=1000000) break; } } void makenum() { bool flag=1; int s,e,i,n=strlen(k),j,sum; shumu=0; for(e=n-1;flag;e=s-1) { if(e-2<=0) { s=0; flag=0; } else s=e-2; sum=0; for(j=s;j<=e;j++) sum=sum*10+(k[j]-'0'); num[shumu++]=sum; } } void iscunzai() { makenum(); int i,j,r; for(i=0;prime[i]<l;i++) { r=0; for(j=shumu-1;j>-1;j--) r=(r*1000+num[j])%prime[i]; if(r==0) { printf("BAD %d\n",prime[i]); return; } } printf("GOOD\n"); } int main() { makeprime(); while(scanf("%s%d",k,&l)&&(k[0]!='0'||l!=0)) { iscunzai(); } }
#include<iostream> #include<cstring> using namespace std; int prime[1000000],sushu,l,num[110],shumu; char k[110]; bool isprime(int x) { int i; if(x%2==0) return 0; for(i=0;prime[i]*prime[i]<=x;i++) if(x%prime[i]==0) return 0; return 1; } void makeprime() { int i; prime[0]=2; for(sushu=1,i=3;;i++) if(isprime(i)) { prime[sushu++]=i; if(i>=1000000) break; } } void makenum() { bool flag=1; int s,e,i,n=strlen(k),j,sum; shumu=0; for(e=n-1;flag;e=s-1) { if(e-3<=0) { s=0; flag=0; } else s=e-3; sum=0; for(j=s;j<=e;j++) sum=sum*10+(k[j]-'0'); num[shumu++]=sum; } } void iscunzai() { makenum(); int i,j; long long r; for(i=0;prime[i]<l;i++) { r=0; for(j=shumu-1;j>-1;j--) r=(r*10000+num[j])%prime[i]; if(r==0) { printf("BAD %d\n",prime[i]); return; } } printf("GOOD\n"); } int main() { makeprime(); while(scanf("%s%d",k,&l)&&(k[0]!='0'||l!=0)) { iscunzai(); } }
另外从这里http://blog.csdn.net/lyy289065406/article/details/6648530学到了一个判断素数的比较快的方法,就是首先判断这个数是不是偶数,如果不是再枚举小于或等于这个数的平方根的素数,看是不是可以使这个数被整除,如果再不是,那么这个数肯定是素数了。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。