首页 > 代码库 > poj 2635 The Embarrassed Cryptographer (同余定理,筛选法)

poj 2635 The Embarrassed Cryptographer (同余定理,筛选法)

链接:poj 2635

题意:给定一个大数k,k是两个大素数的乘积的值,再给定一个int内的数L

      问这两个大素数中最小的一个是否小于L,如果小于则输出这个素数。

分析:因为k达到了10^100,只能用字符串读入,再转化为千进制,用int数组存储,

      然后枚举小于L的素数,看是否能被整除,即判断k%L是否为0,

      这样就得先用筛选法求素数打表,但是注意要打表到大于10^6

      关于高精度取余,就需要用到同余定理

如 123456%N=(((123%N)*1000%N)+456)%N


#include<stdio.h>
#include<string.h>
#define M 1000100
int a[100],k,b[M+10]={1,1,0},p[M+10],num;
void is_prime()    //筛选法求素数
{
    int i,j;
    num=0;
    for(i=2;i<=M;i++)
        if(b[i]==0){
            p[num++]=i;
            for(j=i+i;j<=M;j+=i)
                b[j]=1;
        }
}
int main()
{
    int i,j,n,m,flag,t;
    char s[110];
    is_prime();
    while(scanf("%s%d",s,&n)){
        m=strlen(s);
        if(s[0]=='0'&&n==0) 
            break;
        memset(a,0,sizeof(a));
        k=0;
        t=m%3;
        for(i=0;i<m;i++){  //转化为千进制
            a[k]=a[k]*10+s[i]-'0';
            if((i-t+1)%3==0)
                k++;
        }
        flag=1;
        for(i=0;p[i]<n;i++){ 
            t=0;
            for(j=0;j<k;j++)   //高精度取余
                t=(1000*t+a[j])%p[i];
            if(!t){
                flag=0;
                break;
            }
        }
        if(flag)
            printf("GOOD\n");
        else
            printf("BAD %d\n",p[i]);
    }
    return 0;
}


poj 2635 The Embarrassed Cryptographer (同余定理,筛选法)