(1) (a+b)%c = ((a%c)+(b%c))%c;
(2) (a*b)%c = ((a%c)*(b%c))%c;
Proof:
(1) suppose a=m*c+n, b=s*c+t;
(a+b)%c = ((m*c+n)+(s*c+t))%c = ((m+s)*c+(n+t))%c = ((m+s+k)*c+q)%c = q = (k*c+q)%c = (n+t)%c.
(a+b)%c = ((m*c+n)+(s*c+t))%c = ((m*c+n)%c+(s*c+t)%c)%c=(n+t)%c.
so (a+b)%c = ((a%c)+(b%c))%c;
(2) suppose a=m*c+n, b=s*c+t;
(a*b)%c = ((m*c+n)*(s*c+t))%c = (m*s*c*c+(mt+sn)*c+n*t)%c = ((m*s*c+(mt+sn)+k)*c + q)%c = q = (k*c+q)%c = (n*t)%c.
(a*b)%c = ((m*c+n)%c *(s*c+t)%c)%c = (n*t)%c.
so (a*b)%c = ((a%c)*(b%c))%c;
有了上面两个性质，让我们来看一道题目。给定一个数n(n<10^100), 求 n%145 (char *n);
n[0], n[1], n[2] ... n[length-1].
n=n[0]*10^(length-1) + n[1]*10^(length-2) + ... + n[length-1]. (由于n是字符串，都需要-'0'，为了简便不写了)。
在生成n的时候每一步都取余145.
int ans=0;
for(int i=0; i<length; i++)
ans = (ans*10+n[i])%145;
再来看经典的 快速幂取模 算法：
a^b%n
long long modExp(long long a,long long b,long long n){
long long t,y;
t = 1; y = a;
while(b){
if(b % 2) t = t * y % n;
y = y * y % n;
b >>= 1;
}
return t;
}