【学习笔记】简单数论-同余
同余
- 若整数 \(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 \sim 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}\) 。
- 证明：
欧拉定理
- 若 \(\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}\) 。
扩展欧拉定理
- \(a^b \equiv \begin{cases}a^{b \bmod \varphi(p)} ,\quad \qquad\gcd(a,p)=1\\a^{b} ,\quad \qquad \qquad \ \ \ \ \gcd(a,p) \ne 1,b<\varphi(p)\\a^{b \bmod \varphi(p)+\varphi(p)} ,\quad \gcd(a,p) \ne 1,b \ge \varphi(p)\end{cases} \pmod{p}\)
- 证明极其复杂，请参考 link 或者 oiwiki 中的证明。
- luogu P5091 【模板】扩展欧拉定理
ll read(ll p) { ll x=0,f=1,f2=0; char c=getchar(); while(c<'0'||'9'<c) { if(c=='-') { f=-1; } c=getchar(); } while('0'<=c&&c<='9') { x=x*10+c-'0'; if(x>=p)//当b>=phi(p) 时，公式才能应用 { f2=1; } x%=p; c=getchar(); } if(f2==1) { x+=p; } return x; } ll phi(ll n) { ll ans=n,i; for(i=2;i<=sqrt(n);i++) { if(n%i==0) { ans=ans/i*(i-1); while(n%i==0) { n/=i; } } } if(n>1) { ans=ans/n*(n-1); } return ans; } 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 a,b,phii; cin>>a>>p; phii=phi(p); b=read(phii); cout<<qpow(a,b,p)<<endl; return 0; }
乘法逆元
- 如果存在一个线性同余方程 \(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 提高组] 同余方程
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; } - luoguP2613 【模板】有理数取余
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; }
- 线性求 \(1 \sim n\) 或单个数的逆元（递推/递归）
- 限制条件： \(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; }
- luogu P5431 【模板】乘法逆元 2
ll a[5000001],mul[5000001],invc[5000001],inv; 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,k,i,ans=0,num,inv; n=read(); p=read(); k=read(); mul[0]=1; for(i=1;i<=n;i++) { a[i]=read(); mul[i]=(mul[i-1]*(a[i]%p))%p; } invc[n]=qpow(mul[n],p-2,p); for(i=n-1;i>=1;i--) { invc[i]=(invc[i+1]*(a[i+1]))%p; } num=k%p; for(i=1;i<=n;i++) { inv=(invc[i]*(mul[i-1]%p))%p; ans=(ans+(num*inv)%p)%p; num=(num*k)%p; } write(ans); return 0; } - LibreOJ 161. 乘法逆元 2
ll a[5000001],mul[5000001],invc[5000001],inv[5000001],K[5000001]; 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=1000000007,k=998244353,i,ans=0; n=read(); mul[0]=K[0]=1; for(i=1;i<=n;i++) { a[i]=read(); K[i]=(K[i-1]*(k%p))%p; mul[i]=(mul[i-1]*(a[i]%p))%p; } invc[n]=qpow(mul[n],p-2,p); for(i=n-1;i>=1;i--) { invc[i]=(invc[i+1]*(a[i+1]))%p; } for(i=1;i<=n;i++) { inv[i]=(invc[i]*(mul[i-1]%p))%p; ans=(ans+K[n-i]*inv[i])%p; } write(ans); return 0; }
- 扩展欧几里得