POJ 2635（同余定理）

2019-04-14 16:04发布

站内文章 / 模拟电子
16129 0 1581
题目链接：http://poj.org/problem?id=2635 首先介绍一下同余定理： 所谓的同余，顾名思义，就是许多的数被一个数d去除，有相同的余数。d数学上的称谓为模。如a=6,b=1,d=5,则我们说a和b是模d同余的。因为他们都有相同的余数1。 
　　数学上的记法为： 
　　a≡ b(mod d) 
　　可以看出当n 　　(1) a和b是模d同余的. 
　　(2) 存在某个整数n,使得a=b+nd . 
　　(3) d整除a-b. 
　　可以通过换算得出上面三个都是正确而且是等价的. 
常用公式： 1)a≡a(mod d) 
2)a≡b(mod d)→b≡a(mod d) 
3)(a≡b(mod d),b≡c(mod d))→a≡c(mod d) 

如果a≡x(mod d),b≡m(mod d),则 
4)a+b≡x+m （mod d） 
5)a-b≡x-m (mod d) 
6)a*b≡x*m (mod d ) 
有以上公式可得推论： (a+b)%c=(a%c+b%c)%c;
(a*b)%c=(a%c*b%c)%c;
对于大数的求余，联想到进制转换时的方法，得到
举例如下，设大数 m=1234,模n
就等于((((1*10)%n+2%n)%n*10%n+3%n)%n*10%n+4%n)%n
#include #include #include #include #include #include using namespace std; const int INF=0x3f3f3f3f; const int maxn=105; int T,L; char k[maxn]; int a[maxn]; int prime[1000010]; void work(){//打出100W以内的素数表 memset(prime,0,sizeof(prime)); prime[1]=1; for(int i=2;i<1000010;i++){ if(!prime[i]){ for(int j=2;i*j<1000010;j++){ prime[i*j]=1; } } } int pNum=0; for(int i=1;i<1000010;i++){ if(!prime[i]) prime[pNum++]=i; } } int main(){ #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); freopen("test.out","w",stdout); #endif work(); while(~scanf("%s%d",k,&L)){ if(!strcmp(k,"0")&&!L) break; memset(a,0,sizeof(a)); int len=strlen(k); for(int i=0;i=0;i--) tmp=(tmp*1000+a[i])%prime[index]; if(!tmp){ flag=false; printf("BAD %d ",prime[index]); break; } index++; } if(flag) printf("GOOD "); } return 0; }


热门文章