#The Embarrassed Cryptographer
poj2635题目传送门
题意:给定一个大数，它由两个素数相乘得到，给一个数L，判断大数中较小的因子是否比L小，小则是BAD，否则是GOOD。 简单的一道数论题，麻烦的是这题是大数，用到高精度，可以用数组来存这个数，其中数组a[i]等于大数的每三位，然后枚举小于L的素数，判断是否能整除大数，若能，则为BAD，否为GOOD
#include<stdio.h> #include<string.h> const int MAXN=1000010; int prime[MAXN+1]; void init()//打表 { memset(prime,0,sizeof(prime)); for(int i=2;i<=MAXN;++i) { if(!prime[i]) prime[++prime[0]]=i; for(int j=1;j<=prime[0]&&prime[j]*i<=MAXN;++j) { prime[prime[j]*i]=1; if(i%prime[j]==0) break; } } } int Kt[100]; int L; char str[1000]; bool mod(int *K, int p,int len) { int k = 0; for(int i = len - 1; i >=0; --i) { k = (k * 1000 + K[i]) % p; } if(!k) return false; return true; } int main() { init(); while(scanf("%s %d",&str,&L)!=EOF) { if(L==0&&strcmp(str,"0")==0) break; int len=strlen(str); memset(Kt,0,sizeof(Kt)); //以每千位压入数组中的一个位置， for(int i=0;i<len;i++) { int ii=(len+2-i)/3-1; Kt[ii]=Kt[ii]*10+str[i]-'0'; } int lenKt=(len+2)/3; bool flag=true; int pMin=1; //判断小于L的素数能否整除Kt while(prime[pMin]<L) { if(!mod(Kt,prime[pMin],lenKt)) { flag=false; printf("BAD %d\n",prime[pMin]); break; } pMin++; } if(flag) printf("GOOD\n"); } return 0; }