引用

翱翔天際…… 的 同余定理--大數(shù)求余

這一階段開始著手?jǐn)?shù)論的學(xué)習(xí)……

同余定理，大家都很熟悉吧

(a+b)%c=(a%c+b%c)%c;

(a*b)%c=(a%c*b%c)%c;

對(duì)于大數(shù)的求余，聯(lián)想到進(jìn)制轉(zhuǎn)換時(shí)的方法，得到

舉例如下，設(shè)大數(shù) m=1234,模n

就等于((((1*10)%n+2%n)%n*10%n+3%n)%n*10%n+4%n)%n

寫了一個(gè)簡單的模板

#include<stdio.h>//大數(shù)求余，其中n(除數(shù)）不是大數(shù)
char a[1000];
int main()
{
 int i,j,k,m,n;
 while(scanf("%s%d",a,&n)!=EOF)
 {
  m=0;
  for(i=0;a[i]!='\0';i++)
   m=((m*10)%n+(a[i]-'0')%n)%n;
  printf("%d\n",m);
 }
 return 0;
}