HDU2303（数论）大整数求余+素数筛选

Sample Input

143 10
143 20
667 20
667 30
2573 30
2573 40
0 0

 

Sample Output

GOOD
BAD 11
GOOD
BAD 23
GOOD
BAD 31

 

给你两个数a ，b； 让你求a 的最小素因子是否小于b

枚举小于b 的素数对a进行大整数求余即可。

按照这个栈爆了，看别人对大整数部分进行了处理（感觉对得莫名其妙，稍微改点点就不过╯▽╰/）

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

#include <algorithm>

#pragma comment(linker, "/STACK:102400000,102400000")

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

const int N=1000050;

char p[200];

int q[N],t[N];

int n,L,R,c;

int len;

int tot;

void prim()

{

    int i,j;

    for(i = 2;i < 1000000;i++)

        q[i] = 1;

    for(i= 2,tot = 0; i < 1000000; i++)

    {

        if(q[i])

        {

            t[tot++] = i;

            for(j = i*2; j<1000000; j+=i)

                q[j] = 0;

        }

    }

}

bool work(int m)

{

    int ans = 0;

    for(int i = 0; i < len; i++)

        ans = (int)(((ll)ans*10 + p[i]-'0') % m);

    if(ans == 0)

        return true;

    else

        return false;

}

int main()

{

    int i;

    prim();

    while(scanf("%s%d",p,&c))

    {

        int flag = 1;

        if(c == 0 && p[0] == '0')

            break;

        len = strlen(p);

        for(i = 0; t[i] < c && i <= tot; i++)

            if(work(t[i]))

            {

                flag = 0;

                break;

            }

        if(!flag)

            printf("BAD %d\n",t[i]);

        else

            printf("GOOD\n");

    }

    return 0;

}