数论-北大-2635

[china_sjc]

#include<stdio.h>
#include<string.h>
#define bint __int64
bint maxn;
bint a[11],at;
char ch[101];
int an,range,pn,flag,ln;
bool mark[1000101];
int prime[100001];
int n=12;
void makeprime()
{
int i,j;
mark[0]=mark[1]=1;
for(i=2;i<1000100;i++)
if(!mark[i])
{
prime[pn++]=i;
if(i>1000)continue;
for(j=i*i;j<1000100;j+=i)mark[j]=1;
}
}
void changetoint64()
{
int i,j;
ln=strlen(ch);
an=(ln-1)/n+1;
for(i=0;i<an;i++)
{
a[i]=0;at=1;
for(j=0;j<n;j++)
{
if(ln-1-(i*n+j)<0)break;
a[i]+=(ch[ln-1-(i*n+j)]-48)*at;
at*=10;
}
}
}
int check(int b)
{
int i;
bint g=0;
bint x;
for(i=an-1;i>=0;i--)
{
x=g*maxn+a[i];
g=x%b;
}
if(g==0)
{
if(ln<=n)b=b<a[0]/b?b:a[0]/b;
printf("BAD %d\n",b);
flag=1;
return 1;
}
return 0;
}
int main()
{
int i,j;
makeprime();
maxn=1000000;maxn*=1000000;
while(scanf("%s %d",ch,&range),range)
{
changetoint64();
i=0;flag=0;
j=0;
while(j<pn&&prime[j]<range)j++;
if(prime[j]>=range)j--;
while(i<=j&&check(prime[i])==0&&check(prime[j])==0)i++,j--;
if(flag==0)printf("GOOD\n");
}
return 0;
}