题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2303
题意：给出两个数k, l(4<= k <= 1e100, 2<=l<=1e6)；其中k是两个素数的乘积，问k是否存在严格小于l的因子，若有，输出 BAD 该因子，反之输出GOOD；
思路：
先1e6内素数打表，再枚举一个因子，判断因子用大数取模；
代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAXN 105
#define INF 1000010
using namespace std; int l, prime[INF], vis[INF];
char s[MAXN]; void get_prime(){
int k=;
for(int i=; i<INF; i++){
if(!vis[i]){
prime[k++]=i;
for(int j=; i*j<INF; j++){
vis[i*j]=;
}
}
}
} //**大数取模，(a+b)%m=a%m+b%m, (a*b)%m=(a%m*b%m)%m;
int mod(int m){
int count=, ans=;
for(int i=strlen(s)-; i>=; i--){
int gg=(s[i]-'')*count;
ans=(ans+gg)%m;
count=count*%m;
}
if(ans==){
return ;
}else{
return ;
}
} int main(void){
get_prime();
while(scanf("%s%d", s, &l)){
if(s[]==''&&l==){
return ;
}else{
int flag=;
for(int i=; prime[i]<l; i++){
flag=mod(prime[i]);
if(flag){
printf("BAD %d\n", prime[i]);
break;
}
}
if(flag){
continue;
}
printf("GOOD\n");
}
}
return ;
}