Letters比赛第六场1003 The Embarrassed Cryptographer解题报告

1003 The Embarrassed Cryptographer(POJ 2635)

解题思路：高精度求模+同余模定理+素数打表。注意以下几点：

①素数表不能只打到10^6，必须保证素数表中的最后一个大于10^6。

②读入大数后用千进制（或万进制，十万进制……），用十进制可能会超时。

 

代码如下：

 

#include <cstdlib>
#include <iostream>

using namespace std;

char key[105];
int keyLen = 0;
int num[105];
int numLen = 0;
int primes[1000005];
int cnt = 0;
bool visited[1000005];
int L = 0;
int base = 1;

void getPrimes(int n)
{
    memset(visited, false, sizeof(visited));
    for(int i=2; i<=n; i++)
    {
        if(visited[i] == false)
        {
            primes[cnt++] = i;
            for(int j=i; j<=n; j+=i)
            {
                visited[j] = true;
            }
        }
    }
}

int remainder(int a)
{
    int b = 1;
    __int64 ans = 0;

    for(int j=0; j<base; j++)
    {
        b *= 10;
    }
    for(int i=numLen-1; i>=0; i--)
    {
        ans = b * ans + num[i];
        if(ans >= a)
        {
            ans = ans % a;
        }
    }

    return (int)ans;
}

int main()
{
#ifdef MYLOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    base = 8;//1000
    getPrimes(1000000);

    while(scanf("%s %d", key, &L) != EOF &&
        strcmp(key,"0") && L)
    {
        keyLen = strlen(key);
        numLen = 0;
        memset(num, 0, sizeof(num));

        for(int k=keyLen-base; k+base-1>=0; k-=base)
        {
            for(int j=0; j<base; j++)
            {
                if(k+j >= 0)
                {
                    num[numLen] = 10 * num[numLen] + key[k+j] - '0';
                }
            }
            numLen++;
        }

        bool flag = false;
        for(int i=0; i<cnt && primes[i]<L; i++)/////  i<cnt  ////
        {
            if(remainder(primes[i]) == 0)
            {
                printf("BAD %d\n", primes[i]);
                flag = true;
                break;
            }
        }

        if(flag == false)
        {
            printf("GOOD\n");
        }
    }

    return 0;
}