- 同余
- 若整数 \(a\) 和整数 \(b\) 除以正整数 \(m\) 的余数相等,则称 \(a,b\) 模 \(m\) 同余,记为 \(a \equiv b \pmod{p}\) 。
- 性质
- 自反性: \(a \equiv a \pmod{p}\)
- 对称性:若 \(a \equiv b \pmod{p}\) ,则 \(b \equiv a \pmod{p}\) 。
- 传递性:若 \(a \equiv b \pmod{p},b \equiv c \pmod{p}\) ,则 \(a \equiv c \pmod{p}\) ;若 \(a \equiv b \pmod{p},q|p\) ,则 \(a \equiv b \pmod{q}\) 。
- 同加性:若 \(a \equiv b \pmod{p}\) ,则 \(a+c \equiv b+c \pmod{p}\) 。
- 同乘性:若 \(a \equiv b \pmod{p}\) ,则 \(a \times c \equiv b \times c \pmod{p}\) 。
- 一般情况下不满足同除性。
- 特例:当 \(\gcd(c,p)=1,a \times c\equiv b \times c \pmod{p}\) 时,则 \(a \equiv b \pmod{p}\) 。
- 同幂性:若 \(a \equiv b \pmod{p}\) ,则 \(a^n \equiv b^n\pmod{p}\) 。
- 若 \(p,q\) 互质,\(a \bmod p=x,a \bmod q=x\) ,则 \(a \bmod(p \times q)=x\) 。
- 性质
- 同余类与剩余系
- 对于 \(\forall a \in[0,p-1]\) ,集合 \(\{a+kp\}(k \in \mathbb{Z})\) 的所有数模 \(p\) 同余,余数都为 \(a\) 。该集合称为一个模 \(p\) 的同余类,简记为 \(\overline{a}\) 。
- 模 \(p\) 的同余类一共有 \(p\) 个,分别为 \(\overline{0},\overline{1},\overline{2},...,\overline{p-1}\) 。它们构成 \(p\) 的完全剩余系。
- \(1 \sim p\) 中与 \(p\) 互质的数代表的同余类共有 \(\varphi(p)\) 个,它们构成 \(p\) 的简化剩余系。
- \(p\) 的简化剩余系中的数满足与 \(p\) 互质且模 \(p\) 互不相同。
- 若 \(a,b(1\le a,b\le p)\) 与 \(p\) 互质,有 \(a,b,(a \times b) \bmod p\) 属于 \(p\) 的简化剩余系。
- 费马小定理
- 若 \(p\) 是质数,则对于任意整数 \(a\) ,有 \(a^p \equiv a \pmod{p}\) 。
- 证明:
- 当 \(a\) 是 \(p\) 的倍数时,显然结论成立。
- 当 \(a\) 不是 \(p\) 的倍数时,不存在一组 \(x,y\) 满足 \(1 \le x,y<p,xa \equiv ya \pmod{p}\) 。因此 \(1 \sim p-1\) 所有数,乘以 \(a\) 之后对 \(p\) 取模,仍可得 \(1\) ~ \(p-1\) 所有数。则 \(\prod\limits_{i=1}^{p-1} i \equiv \prod\limits_{i=1}^{p-1} ai \pmod{p}\) ,易知其中 \(\prod\limits_{i=1}^{p-1} i\) 与 \(p\) 互质,则 \(\prod\limits_{i=1}^{p-1}a \equiv 1 \pmod{p}\) ,即 \(a^{p-1} \equiv 1 \pmod{p}\) 。等式两边同乘 \(a\) ,得到 \(a^p \equiv a \pmod{p}\) 。
- 变形
- 若 \(\gcd(a,p)=1\) ,即 \(a\) 不是 \(p\) 的倍数,有 \(a^{p-1} \equiv 1 \pmod{p}\) 。
- 若 \(\gcd(a,p) \ne 1\) ,即 \(a\) 是 \(p\) 的倍数,有 \(a^{p-1} \equiv 0 \pmod{p}\) 。
- 证明:
- 若 \(p\) 是质数,则对于任意整数 \(a\) ,有 \(a^p \equiv a \pmod{p}\) 。
- 欧拉定理
- 若 \(\gcd(a,p)=1\) ,则 \(a^{\varphi(p)} \equiv 1 \pmod{p}\) 。
- 证明:
- 当 \(p\) 为质数时,有 \(a^{\varphi(p)}=a^{p-1}\) ,依据费马小定理,有 \(a^{p-1} \equiv 1 \pmod{p}\) 。
- 当 \(p\) 不为质数时,设 \(S=\{ p_1,p_2,...,p_{\varphi(p)}\}\)为 \(p\) 的简化剩余系,对于任意一对 \(i,j(i \ne j)\) ,有 \((a \times p_i) \bmod p \ne (a \times p_j) \bmod p\) ,且 \(a \times p_i,a \times p_j\) 均与 \(p\) 互质。因此 \(S\) 中所有数,乘以 \(a\) 之后对 \(p\) 取模,仍可得 \(S\) 中所有数,则 \(\prod\limits_{i=1}^{\varphi(p)} i \equiv \prod\limits_{i=1}^{\varphi(p)} ai \pmod{p}\) ,易知其中 \(\prod\limits_{i=1}^{\varphi(p)} i\) 与 \(p\) 互质,则 \(\prod\limits_{i=1}^{\varphi(p)}a \equiv 1 \pmod{p}\) ,即 \(a^{\varphi(p)} \equiv 1 \pmod{p}\) 。
- 扩展欧拉定理
- 乘法逆元
- 如果存在一个线性同余方程 \(ax \equiv 1 \pmod{b}\) ,则 \(x\) 记作 \(a \bmod b\) 的乘法逆元(简称逆元),记作 \(a^{-1}\) 。
- 若 \(b|a\) 时不存在 \(a\) 的逆元 \(a^{-1}\) 。
- 特别地,有 \(1^{-1} \equiv 1 \pmod{b}\) 。
- 证明:对于 \(\forall b \in \mathbf{Z}\) ,有 \(1 \times 1 \equiv 1 \pmod{b}\) ,故在 \(b\) 下 \(1\) 的逆元为 \(1\) 。
- 性质
- 若 \(n\) 为正整数,则 \(2 \bmod(2n+1)\)的乘法逆元为 \(n+1\) 。
- 证明:已知 \(2x \equiv 1 \pmod{2n+1}\) ,设 \(2x=(2n+1)k+1\) ,又因为 \(2x\) 为偶数, \(k\) 的最小正整数解为 \(1\) ,代入得 \(x=n+1\) 。
- 若 \(n\) 为正整数,则 \(2 \bmod(2n+1)\)的乘法逆元为 \(n+1\) 。
- 如何求逆元(边算边取模)
- 扩展欧几里得
- 限制条件: \(\gcd(a,b)=1\) 。
- 设 \(ax=bk+1,y=-k\) ,原方程可改写为 \(ax+by=1\) ,用 \(exgcd\) 解得一组特解 \(x_0,y_0\) ,\(x\) 的最小正整数解为 \((x+b)\bmod b\) 。
- 时间复杂度为 \(O(\log \max(a,b))\) 。
- luogu P1082 [NOIP2012 提高组] 同余方程
luoguP2613 【模板】有理数取余ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } else { ll d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } } int main() { ll a,b,x=0,y=0; cin>>a>>b; exgcd(a,b,x,y); x=(x%b+b)%b; cout<<x<<endl; }
const ll p=19260817; ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } else { ll d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } } int main() { ll a,c,d,x=0,y=0; c=read(); a=read(); d=exgcd(a,p,x,y); if(c%d==0) { x=(x*c/d)%p; x=(x%p+p)%p; cout<<x<<endl; } else { cout<<"Angry!"<<endl; } return 0; }
- 扩展欧几里得
- 快速幂+费马小定理/欧拉定理
- 限制条件: \(b\) 为质数。
- 因为 \(b\) 为质数, \(ax \equiv 1 \pmod{b}\) ,依据费马小定理/欧拉定理,则 \(ax \equiv a^{b-1} \pmod{b}\) ,故 \(x \equiv a^{b-2} \pmod{b}\) 。用快速幂求出 \(a^{b-2} \bmod b\) ,即为所求。
- 时间复杂度为 \(O(\log b)\) 。
- luogu P1082 [NOIP2012 提高组] 同余方程
ll qpow(ll a,ll b,ll p) { ll ans=1; a%=p; while(b>0) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans%p; } int main() { ll a,b; cin>>a>>b; cout<<qpow(a,b-2,b)<<endl; }
- 线性求逆元(递推/递归)
- 限制条件: \(b\) 为质数。
- 设 \(k=\left\lfloor\dfrac{b}{i}\right\rfloor,r=b \bmod i\) ,此时有 \(b=k \times i+r,r<i\) ,进而得到 \(k \times i+r\equiv 0 \pmod{b}\) 。两边同时乘以 \(i^{-1} \times r^{-1}\) 得 \(k \times r^{-1}+i^{-1}\equiv 0 \pmod{b}\) ,移项得 \(i^{-1}\equiv -k \times r^{-1} \pmod{b}\) ,将 \(k=\left\lfloor\dfrac{b}{i}\right\rfloor,r=b \bmod i\) 代入得 \(i^{-1}\equiv -\left\lfloor\dfrac{b}{i}\right\rfloor \times (b \bmod i)^{-1} \pmod{b}\) ,考虑消除负数取模对答案的影响,故推出逆元:\(\\i^{-1} \equiv \begin{cases}1,&i=1\\(b-\left\lfloor\dfrac{b}{i}\right\rfloor) \times (b \bmod i)^{-1}&otherwise\end{cases} \pmod{b}\)
- 递推求 \(N\) 个数的逆元, \(O(N)\) 预处理, \(O(1)\) 查询。
- 递归+记忆化求 \(N\) 个数的逆元, \(O(N)\) 预处理, \(O(1)\) 查询。
- 递归求 \(n\) 的逆元,时间复杂度为 \(O(n^{\dfrac{1}{3}})\) 。
- luogu P3811 【模板】乘法逆元
ll inv[3000001]; int main() { ll n,p,i; cin>>n>>p; inv[1]=1; cout<<"1"<<endl; for(i=2;i<=n;i++) { inv[i]=(p-p/i)*inv[p%i]%p; cout<<inv[i]<<endl; } return 0; }
- 线性求任意 \(n\) 个数的逆元(离线)
- 限制条件: \(b\) 为质数。
- 给定一个长度为 \(n\) 的序列 \(a(1 \le i \le n,1 \le a_i <p)\) ,分别求出 \(a_i^{-1}(1 \le n)\) 。令 \(mul[i]=\prod\limits_{k=1}^{i} a_i\) ,利用 \(exgcd\) 或快速幂计算 \(invc[n]=mul[n]^{-1}\) ,此时有 \(invc[i]=invc[i+1] \times a_{i+1}=mul[i]^{-1}\) ,那么 \(a_i^{-1}=mul[i-1] \times invc[i]\) 。
- 时间复杂度为 \(O(n+\log b)\) 。
- luogu P3811 【模板】乘法逆元
ll mul[3000001],invc[3000001],inv[3000001],w[3000001];//防止重名,此处的w[]即为上文的a[] ll qpow(ll a,ll b,ll p) { ll ans=1; while(b>0) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans%p; } int main() { ll n,p,i; cin>>n>>p; mul[0]=1; for(i=1;i<=n;i++) { w[i]=i; mul[i]=((mul[i-1]%p)*(w[i]%p))%p; } invc[n]=qpow(mul[n],p-2,p); for(i=n-1;i>=1;i--) { invc[i]=((invc[i+1]%p)*((w[i+1])%p))%p; } for(i=1;i<=n;i++) { inv[i]=((invc[i]%p)*(mul[i-1]%p))%p; cout<<inv[i]<<endl; } return 0; }
- 如果存在一个线性同余方程 \(ax \equiv 1 \pmod{b}\) ,则 \(x\) 记作 \(a \bmod b\) 的乘法逆元(简称逆元),记作 \(a^{-1}\) 。
- 若整数 \(a\) 和整数 \(b\) 除以正整数 \(m\) 的余数相等,则称 \(a,b\) 模 \(m\) 同余,记为 \(a \equiv b \pmod{p}\) 。