同余（模）定理

同余定义（德国/高斯）：

两个整数 a、b，如果他们同时除以一个自然数p，所得的余数相同，则称a,b对于模p同余，记作a≡b（mod p）。读作：a同余于b模m。

性质

1. (a + b) % p = (a % p + b % p) % p
2. (a - b) % p = ( (a % p - b % p) + p ) % p
3. (a * b) % p = (a % p) * (b % p) % p
4. 若 a ≡ b(mod p)，则 (a - b) mod p ≡ 0
5. 若 a ≡ b(mod p)，则 (a ^ n) mod p ≡ (b ^ n) mod p

例题

求 2001 ^ 2003 % 13

解

2001 % 13 = 12，即2001 同余于 12 （模13）

根据性质5，原问题等于求 12 ^ 2003 % 13

找出 12 的几次幂 同余于 1 （模13），发现 12 ^ 2 ≡ 1 (mod 13)

(12 ^ 2003) % 13 = [ (12 ^ 2) ^ 1001 * (12 ^ 1)] % 13

根据性质5， 上式 = [ (1 ^ 1001) * (12 ^ 1) ] % 13 = 12

也就口算笔算可以，用程序写出来实用性弱，远不如快速幂万能（在适合的情况下比快速幂快）

Code

int same_remainer(int a, int b, int c)
{
    a = a % c;
    int t = 0;
    for(int i = 1; i < sqrt(b); ++i)
    {
        if(int(pow(a, i)) % c == 1)
        {
            t = i;
            break;
        }
    }
    for(int i = 0; t != 0; ++i)
        if((b - i) % t == 0)
        {
            b = i;
            break;
        }
    return (int)pow(a, b) % c;
}

大数（高精度）求余

1234 = ( (1 * 10 + 2) * 10 + 3 ) * 10 + 4

利用性质1、3可解

1234 % n = ((((1 * 10 ) % n + 2 % n) % n * 10 % n + 3 % n) % n * 10 % n + 4 % n) % n

Code(大数求余)

#include <string>
#include <iostream>
using namespace std;

int main()
{
    string a;
    int n;
    while(cin >> a >> n)
    {
        int ans = 0;
        int sz = a.size();
        for(int i = 0; i < sz; ++i)
            ans = ((ans * 10) % n + (a[i] - '0') % n) % n;
        cout << ans << '\n';
    }
    return 0;
}