题目:http://poj.org/problem?id=2635
高精度求模 同余模定理。
题意:
给定一个大数K,K是两个大素数的乘积的值。再给定一个int内的数L
问这两个大素数中最小的一个是否小于L,如果小于则输出这个素数。
思路:
Char格式读入K。把K转成千进制Kt,同时变为int型。
把数字往大进制转换能够加快运算效率。若用十进制则耗费很多时间,会TLE。千进制的性质与十进制相似。
例如,把K=1234567890转成千进制,就变成了:Kt=[ 1][234][567][890]。 //不过我现在还不明白为什么不是123 456 789 0
当123是一个大数时,就不能直接求,只能通过同余模定理对大数“分块”间接求模
具体做法是:
先求1%3 = 1
再求(1*10+2)%3 = 0
再求 (0*10+4)% 3 = 1
那么就间接得到124%3=1,这是显然正确的
而且不难发现, (1*10+2)*10+4 = 124
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; int p[];
int kt[],l,lenkt;
void prime()
{
int i,j;
memset(p,-,sizeof(p));
p[]=p[]=;
for(i=; i<; i++)
{
if(i%==) p[i]=;
if(p[i])
for(j=i*; j<; j+=i)
p[j]=;
}
//cout<<p[31]<<endl;
} int check()
{
int i=,j,mo;
while(i<l)
{
mo=;
if(p[i])
{
for(j=; j<=lenkt; j++)
mo=(mo*+kt[j])%i;
if(mo==)
return i;
}
i++;
}
return ;
} int main()
{
prime();
char s[];
int i,j,len,x,y;
int cnt;
while(cin>>s>>l&&(strcmp(s,"")!=||l!=))
{
len=strlen(s);
j=; x=;
memset(kt,,sizeof(kt)); y=len%;
if(y==)
lenkt=len/;
else
{
lenkt=len/+;
for(i=; i<y; i++)
kt[x]=kt[x]*+s[i]-;
x++;
}
for(i=y; i<=len-; i++)
{
kt[x]=kt[x]*+s[i]-;
j++;
if(j%==)
x++;
}
//cout<<lenkt<<" "<<kt[1]<<" "<<kt[2]<<endl;
cnt=check();
if(cnt)
printf("BAD %d\n",cnt);
else
printf("GOOD\n");
}
return ;
}