大数同余定理

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

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring> 
using namespace std;
char a[1000];
int n,i;
int main()
{
	while (~scanf("%s%d",a,&n))
	{
		int m=0;
		int l=strlen(a);
		for (i=0;i<l;i++)
			m=((m*10)%n+(a[i]-'0'))%n;
		cout<<m<<endl;
	}
	return 0;
}

以下转自wiki百科"同余":http://zh.wikipedia.org/wiki/%E5%90%8C%E9%A4%98

数学上，当两个整数除以同一个正整数，若得相同余数，则二整数同余。同余理论常被用于数论中。最先引用同余的概念与“≡”符号者为德国数学家高斯。

同余符号

两个整数

记作

读作

比如

同余于的符号是同余相等符号?≡。统一码值为 U+2261。但因为方便理由，人们有时会把它(误)写为普通等号 (=)。

整除性

传递性

保持基本运算

除法原理

欧拉定理

威尔逊定理

整除多项式

因为

例子

• 求自然数a的个位数字，就是求a与哪一个数对于模10同余。

• 

  。

• 注释[编辑]

  1. ^?^1.0?^1.1?

     

     ?表示 m 能整除?x，或者说 x 能被 m 整除。
  2. ^?

     

     表示

     

     的最大公约数。
  3. ^?

     

     表示

     

     的最小公倍数。