数学同余定理

## 同余 ### 定义 如果 $a\ \%\ m=b\ \%\ m(m\mid a-b)$，则 $a$ 与 $b$ 对于 $m$ 同余，或者说 $a$ 同余于 $b$ 模 $m$，记作 $a\equiv b\pmod m$。 #### 定理 1. $a\equiv b\pmod m$，当且仅当 $m\mid(a-b)$； 2. $a\equiv b\pmod m$，当且仅当存在 $k$ 使得 $a=b+m\times k$。 #### 性质 - 自反性：$a\equiv a\pmod m$； - 对称性：若 $a\equiv b\pmod m$，则 $b\equiv a\pmod m$； - 传递性：若 $a\equiv b\pmod m,b\equiv c\pmod m$，则 $a\equiv c\pmod m$； - 同加性：若 $a\equiv b\pmod m$，则 $a+c\equiv b+c\pmod m$； - 同乘性：若 $a\equiv b\pmod m$，则 $a\times c\equiv b\times c\pmod m$； - 同幂性：若 $a\equiv b\pmod m$，则 $a^c\equiv b^c\pmod m$； - 分配性一：$a\times b\mod m=(a\mod m)\times (b\mod m)\mod m$； - 分配性二：$(a+b)\mod m=((a\mod m)+(b\mod m))\mod m$； - $a\equiv b\pmod m$ 并且 $c\equiv d\pmod m$，则 $a\times c\equiv b\times d\pmod m$； - $a\mod p=x,a\mod q=x$ 并且 $q$ 和 $p$ 互质，则 $a\mod p\times q=x$。 ### 快速幂 给定三个整数 $x$、$y$ 和 $m$（\leq x,y\leq 10^9$，\leq m\leq 10^9$），求 $x^y\mod m$ 的值。 让我们以求 ^{89}\mod 7$ 为讲解。 #### 方法一 我们将 $y$ 分解成 $ 的幂次方（因为任何数都可以拆解成 $ 的幂方和），然后根据前一项的值求出后一项的值，最后相乘求解。 - ^1\equiv 3\pmod 7$；（^1\mod 7=1$） - ^2\equiv (3^1)^2\pmod 7\equiv 2\pmod 7$；（^2\mod 7=2$） - ^4\equiv (3^2)^2\pmod 7\equiv 2^2\pmod 7\equiv 4$；（^4\mod 7=4$） - ^8\equiv (3^4)^2\pmod 7\equiv 4^2\pmod 7\equiv 2$；（^8\mod 7=2$） - ^{16}\equiv (3^8)^2\pmod 7\equiv 2^2\pmod 7\equiv 4$；（^{16}\mod 7=4$） - ^{32}\equiv (3^{16})^2\pmod 7\equiv 4^2\pmod 7\equiv 2$；（^{32}\mod 7=2$） - ^{64}\equiv (3^{32})^2\pmod 7\equiv 2^2\pmod 7\equiv 4$；（^{64}\mod 7=4$） 易得 ^{89}=3^{64+32+8+1}=3^{64}\times 3^{32}\times 3^8\times 3^1$，然后得出： $^{89}\equiv 3^{64}\times 3^{32}\times 3^8\times 3^1 \pmod 7\equiv 4\times 4\times 2\times 3\pmod 7\equiv 96\pmod 7\equiv 5\pmod 7$$ 综上所诉，^{89}\mod 7=5$。 #### 方法二 我们可以轻易地推出： - $x^y=x\times x^{y-1}$； - $x^y=x^{y\times 2\div 2}=x^{2\times {y\over2}}=(x^2)^{y\over 2}$。 然后得到以下递推式： $x^y = \begin{cases} 1 & y=0 \\\ x\times x^{y-1} &y\mod 2=1\\\ (x^2)^{y\over 2} &y\mod 2=0\end{cases}$ 也就是递归对 $y$ 进行二进制分解（$x^{y}=x\times x^{y-1}$ 这类初二知识后面不会再做解释了）： $^{89}=(3^{44})^2\times 3=((3^{22})^2)^2\times 3=(((3^{11})^2)^2)^2\times 3=((((3^5)^2\times 3)^2)^2)^2\times 3=(((((3^2)^2 \times 3)^2\times 3)^2)^2)^2\times 3$$ 最后计算，每次都进行取模运算，就能保证能在一定的范围内完成运算。 #### 参考代码 注意这里的代码是求 $x^p\mod m$ 的值。 ```cpp #include <iostream> using namespace std; typedef long long LL; LL fun(LL x, LL p, LL m){ if(p == 0) return 1; if(p == 1) return x; if(p % 2 == 0){ LL t = fun(x,p/2,m); return t * t % m; }else{ LL t = fun(x,p/2,m); t = t * t % m; t = t * x % m; return t; } return -1; } int main(){ LL x,p,m,ans=1; cin >> x >> p >> m; cout << fun(x,p,m) << endl; while(p != 0){ if(p % 2 == 1) ans = ans * x % m; x = x * x % m; p = p / 2; } cout << ans << endl; return 0; } ```