【题意】：给出一个数k(4<=k<=10
100)和L(L<=10
6)，问k的最小质因数是否小于L。
【题解】：显然我们只关心质因数，所以先对L求出它的所有质因数。
然后就是判断这些质因数是否能够整除k，如果用十进制高精度去求模会TLE。
考虑到进制越大，运算的次数就越少。因此我们可以更高的进制。
我测试了两种进制，1000进制时800+MS，10000000000进制时500+MS。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 #define maxn 110
22 #define maxl 1000050
23 char s[maxn];
24 int l, cnt;
25 int prime[100000], pn;
26 ll val[maxn];
27
28 void getprime() {
29 bool isprime[maxl];
30 memset(isprime, true, sizeof(isprime));
31 pn = 0;
32 for(ll i = 2; i < maxl; i++) {
33 if(isprime[i]) {
34 prime[pn++] = i;
35 for(ll j = i * i; j < maxl; j += i) isprime[j] = false;
36 }
37 }
38 }
39
40 void work() {
41 int len = strlen(s);
42 ll res = 0;
43 cnt = 0;
44 for(int i = 0; i < len % 10; i++) {
45 res *= 10;
46 res += s[i] - '0';
47 }
48 val[cnt++] = res;
49 for(int i = len % 10; i < len; i += 10) {
50 res = 0;
51 for(int j = i; j < i + 10; j++) {
52 res *= 10;
53 res += s[j] - '0';
54 }
55 val[cnt++] = res;
56 }
57 }
58
59 int main() {
60 getprime();
61 while(~scanf("%s%d", s, &l)) {
62 if(s[0] == '0' && l == 0) break;
63 work();
64 bool flag = true;
65 int len = (strlen(s) + 9) / 10;
66 for(int i = 0; i < pn && prime[i] < l; i++) {
67 ll res = 0;
68 for(int j = 0; j < cnt; j++) {
69 res = res * 10000000000LL + val[j];
70 res %= prime[i];
71 }
72 if(res == 0) {
73 printf("BAD %d\n", prime[i]);
74 flag = false;
75 break;
76 }
77 }
78 if(flag) printf("GOOD\n");
79 }
80 return 0;
81 }
82