POJ 2635 The Embarrassed Cryptographer

Description

The young and very promising cryptographer Odd Even has implemented the security module of a large system with thousands of users, which is now in use in his company. The cryptographic keys are created from the product of two primes, and are believed to be secure because there is no known method for factoring such a product effectively.

What Odd Even did not think of, was that both factors in a key should be large, not just their product. It is now possible that some of the users of the system have weak keys. In a desperate attempt not to be fired, Odd Even secretly goes through all the users keys, to check if they are strong enough. He uses his very poweful Atari, and is especially careful when checking his boss’ key.

Input

The input consists of no more than 20 test cases. Each test case is a line with the integers 4 <= K <= 10100 and 2 <= L <= 106. K is the key itself, a product of two primes. L is the wanted minimum size of the factors in the key. The input set is terminated by a case where K = 0 and L = 0.

Output

For each number K, if one of its factors are strictly less than the required L, your program should output “BAD p”, where p is the smallest factor in K. Otherwise, it should output “GOOD”. Cases should be separated by a line-break

Sample Input

143 10
143 20
667 20
667 30
2573 30
2573 40
4 2
6 3
6 3
15 3
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689     2
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689     3
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689     999981
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689     999982
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689     999983
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689     999984
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999536689     999985
9936798836621706335903766366605021199756127575438907144689843371764114998372849970522970722679648297     1000000
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999924165887     1000000
9999999999999999997709341477512928270733515750111494296807693217401592660013176273247584305454312971     1000000
9999999999988881245087379264540384030358544520360773252628174690915590034078934845096473005364364269     1000000
9999999999999999999999999999999999999999999999999999999999999999999997947710886296926452585995644787     1000000
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998743929569     1000000
9999999999999999999999999999999999999999999999999999999999999999999999996406876316697599258447653751     1000000
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995271511     1000000
9999664515006205757944572422495695942633452678405393581216966782816097132509526872495414067984894021     1000000
0 0

Sample Output

GOOD
BAD 11
GOOD
BAD 23
GOOD
BAD 31
GOOD
BAD 2
BAD 2
GOOD
GOOD
GOOD
GOOD
GOOD
GOOD
BAD 999983
BAD 999983
BAD 587
BAD 100043
GOOD
GOOD
GOOD
GOOD
GOOD
BAD 16603
BAD 9103

题解 https://blog.csdn.net/lyy289065406/article/details/6648530

My Code

#include <ctime>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000005;

bool vis[N + 5];
///我RE了一下午四处改动，最后竟是因为vis[N]这里小了！！！
///因为会访问vis[N],数组开到N，自然最后到 N - 1
int p[N + 5];
int tot;
int k[105];///千进制下的K
int L;

void get_prime()
{
//    clock_t start, over;
//    start = clock();
    tot = 0;
    memset(vis, 1, sizeof(vis));///初始化全为素数
    vis[0] = vis[1] = 0;
    for(int i = 2; i <= N; ++i)
    {
        if(vis[i])
            p[++tot] = i;
        for(int j = 1; j <= tot && p[j] * i <= N; ++j)
        {
            vis[ p[j] * i ] = 0;
            if(i % p[j] == 0)
                break;
        }
    }
//    over = clock();
//    cout << (double)(over - start) / CLOCKS_PER_SEC << "(s)" << '\n';
//    cout << "tot : " << tot << '\n';
    return ;
}

///大数（高精度）取模
bool mod(int * k, int len, int p)
{
    int ans = 0;
    for(int i = len - 1; i >= 0; --i)///逆序存放的
        ans = (ans * 1000 + k[i]) % p;///同余模定理
    if(!ans)///被整除
        return 1;
    else
        return 0;
}

int main()
{
    get_prime();
    char sk[105];
//    freopen("00in.txt", "r", stdin);
    while(cin >> sk >> L && L)
    {
        memset(k, 0, sizeof(k));
        int sklen = strlen(sk);
        ///十进制转千进制（局部“顺序”， 全局“逆序”）
        ///如K=1234567=[  1][234][567] ，则Kt=[567][234][1  ]
        for(int i = 0; i < sklen; ++i)
        {
            int num = (sklen + 2 - i) / 3 - 1;
            k[num] = k[num] * 10 + (sk[i] - '0');
        }
        int klen = (sklen + 2) / 3;

        bool flag = 1;
        int idx = 1;///从第1个素数开始找
        while(p[idx] < L)
        {
            if(mod(k, klen, p[idx]))
            {
                flag = 0;
                cout << "BAD " << p[idx] << '\n';
                break;
            }
            idx++;
        }
        if(flag)
            cout << "GOOD" << '\n';
    }
    return 0;
}