The Embarrassed Cryptographer POJ - 2635 同余模+高精度处理 +线性欧拉筛（每n位一起处理）

题意：给出两数乘积K（1e100） 和 一个数L(1e6)  问有没有小于L（不能等于）的素数是K的因数

思路：把数K切割 用1000进制表示   由同余模公式知   k%x=(a*1000%x+b*1000*1000%x+c*1000*1000*1000%x....)

a b c等为 相应位置的三位数  这样切割可以减少模的次数 防止超时

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<cmath>

 #include<iostream>

 using namespace std;

 const int maxn=1e6+;

 int primes[maxn];

 int vis[maxn];

 int cnt;

 void init(){

      cnt=;

     for(int i=;i<maxn;i++){

         if(!vis[i])primes[cnt++]=i;

         for(int j=;j<cnt&&i*primes[j]<maxn;j++){

             vis[i*primes[j]]=;

             if(i%primes[j]==)break;

         }

     }

 }

 char k[];

 int kt[];

 int l;

 int lenkt;

 bool check(int prime){

     int ans=;

     for(int i=lenkt-;i>=;i--){

         ans=(ans*+kt[i])%prime;

     }

     if(ans==)return ;

     return ;

 }

 int main(){

     init();

     while(scanf("%s%d",k,&l)==&&l&&k[]!=''){

         int len=strlen(k);

         memset(kt,,sizeof(kt));

         for(int i=;i<len;i++){

             int temp=(len-i+)/-;//从后往前3个3个数 +2向上取整

             kt[temp]=kt[temp]*+k[i]-'';

         }

          lenkt=(len+)/;//+2是向上取整

          int flag=;

          for(int i=;i<cnt&&primes[i]<l;i++){

              if(check(primes[i])){

                  printf("BAD %d\n",primes[i]);

                  flag=;

                  break;

              }

          }

          if(!flag){

              printf("GOOD\n");

          }

     }

     return ;

 }