2015年5月17日
题目大意，给你一个数K（4 <= K <= 10^100）和一个 L（2<=L<=10^6），K是由两个因子组成，若K最小的因子大于等于L，输出 GOOD，否则输出BAD和这个小于L的因子。多组输入，最多20组。
K这个数很大，不能用基本的数据类型处理，应用高精度来做，用一个字符数组来模拟。很容易想到的一个做法是，用高精度模拟出这个数，然后枚举K的因子x（2- L），若K除这个数x等于0，则就找到一个K的因子x，并且这个因子是小于L的，所以输出BAD x。若没有找到一个x能被K整除，则输出GOOD。分析一下时间复杂 度，对于每个K需要枚举的数是2-L这个范围，这里就是100*10^6,还有20组测试数据，所以总的时间复杂度是O（20*100*10^6），题目限制是3000MS，很明 显这里是过不了的。这里有一个优化方法，就是用埃氏素筛法将2-10^6的素数筛 选出来放在prim[]数组里，对于每个K，只需枚举2-L之间的素数就可以了，这 样你还是不能AC。还可以做一个优化，用一个10^12进制的数来模拟这个K。
所以，解决此题的方法：高精度模拟，用埃氏素筛将2-10^5的数筛选出来，用10^12进制模拟。
贴出代码，供大家参考。
#include <cstdio>
#include <cstring>
#define maxn 1000007
#define MAXN 101
#define LL long long
LL prim[maxn];
LL arr[MAXN];
bool is_prim[maxn];
int Init()
{for(int i = 2; i * i < maxn; ++i){if(!is_prim[i])for(int j = 2 * i; j < maxn; j += i)is_prim[j] = true;}int pos = 0;for(LL i = 2; i < maxn; ++i)if(!is_prim[i]) prim[pos++] = i;return pos;
}
int main()
{int N = Init();char ch[MAXN];int L;while(scanf("%s%d", ch, &L), ch[0] != '0', L){int len = strlen(ch), pos = 0, num = 12, p = len % num;LL val = 1;while(p--) val *= 10;for(int i = 0; i < len; i += num){LL val = 0;for(int j = i; j < i + num && j < len; ++j)val = val * 10 + ch[j] - '0';arr[pos++] = val;}bool flag = true;for(int i = 0; prim[i] < L && i < N; ++i){LL Mod = 0;for(int j = 0; j < pos; ++j){if(j != pos - 1) Mod = (Mod * 1000000000000 + arr[j]) % prim[i];else Mod = (Mod * val + arr[j]) % prim[i];}if(Mod == 0){printf("BAD %d\n", prim[i]);flag = false;break;}}if(flag) puts("GOOD");}return 0;
}