定义
? 若整数 \(a\) 和整数 \(b\) 除以正整数 \(m\) 的余数相等, 则称 \(a,b\) 模 \(m\) 同余, 记为 \(a\equiv b\ (mod\ m)\) .
同余系与剩余系
? 对于 \(\forall a\in[0,m-1]\) , 集合 {\(a+km\)} \((k\in\N)\) 的所有数模 \(m\) 同余, 余数都是 \(a\) . 该集合称为一个模 \(m\) 的同余类, 简记为 \(\bar{a}\) .
? 模 \(m\) 的同余类一共有 \(m\) 个, 分别为 \(\bar{0},\bar{1},\cdots,\overline{m-1}\) . 它们构成 \(m\) 的完全剩余系.
? \(1\sim m\) 中与 \(m\) 互质的数代表的同余类共有 \(\varphi(m)\) 个, 它们构成 \(m\) 的简化剩余系.
? 简化剩余系关于模 \(m\) 乘法封闭. 这是因为若 \(a,b(1\leq a,b\leq m)\) 与 \(m\) 互质, 则 \(a*b\) 也不可能与 \(m\) 有相同的质因子, 即 \(gcd(a*b,m)=1\) . 再由余数的定义可知 \(a*b\ mod\ m\) 也与 \(m\) 互质, 即 \(a*b\ mod\ m\) 也属于 \(m\) 的简化剩余系.
欧拉定理
费马小定理
? 若 \(p\) 是质数, 则对于任意整数 \(a\) , 有 \(a^p\equiv a\ (mod\ p)\) .
欧拉定理
? 若正整数 \(a,n\) 互质, 则 \(a^{\varphi(n)}\equiv 1\ (mod\ n)\) .
证明:
? 设 \(n\) 的简化剩余系为 {\(\overline{a_1},\overline{a_2},\cdots,\overline{a_{\varphi(n)}}\)}. 对 \(\forall a_i,a_j\) , 若 \(a*a_i\equiv a*a_j\ (mod\ n)\) , 则 \(a*(a_i-a_j)\equiv 0\) . 因为 \(a,n\) 互质, 所以 \(a_i-a_j\equiv 0\) , 即 \(a_i\equiv a_j\) . 故当 \(a_i\not= a_j\) 时, \(aa_i,aa_j\) 也代表不同的同余类.
? 又因为简化同余系关于模 \(n\) 乘法封闭, 故 \(\overline{aa_i}\) 也在简化剩余系中. 因此, 集合 {\(\overline{a_1},\overline{a_2},\cdots,\overline{a_{\varphi(n)}}\)} 与集合 {\(\overline{aa_1},\overline{aa_2},\cdots,\overline{aa_{\varphi(n)}}\)} 都能表示 \(n\) 的简化剩余系. 综上所述: \(a^{\varphi(n)}a_1a_2\cdots a_{\varphi(n)}\equiv(aa_1)(aa_2)\cdots(aa_{\varphi(n)})\equiv a_1a_2\cdots a_{\varphi(n)}\ (mod\ n)\)
? 因此 \(a^{\varphi(n)}\equiv1\ (mod\ n)\) .
? 当 \(p\) 是质数时, \(\varphi(n)=n-1\) , 并且只有 \(p\) 的倍数与 \(p\) 不互质. 所以, 只要 \(a\) 不是 \(p\) 的倍数, 就有 \(a^{p-1}\equiv1\ (mod\ p)\) , 两边同乘 \(a\) 就是费马小定理. 另外, 若 \(a\) 是 \(p\) 的倍数, 费马小定理显然成立.
? 证毕.
欧拉定理的推论
? 若正整数 \(a,n\) 互质, 则对于任意正整数 \(b\) , 有 \(a^b\equiv a^{b\ (mod\ \varphi(n))}\ (mod\ n)\) .
? 对于一些计数类题目, 如果要计算乘方算式, 根据欧拉定理, 可以先把底数对 \(p\) 取模, 指数对 \(\varphi(n)\) 取模. 再计算乘方.
? 特别的, 当 \(a,n\) 不一定互质且 \(b>\varphi(n)\) 时, 有 \(a^b\equiv a^{b\ mod\ \varphi(n)+\varphi(n)}\ (mod\ n)\). 这意味着即使底数和模数不互质, 我们也有办法把指数的规模缩小到容易计算的范围内. 上式可以通过寻找 \(a^b\ mod\ n\) 的指数循环节证明.
例题
题面
题面 http://poj.org/problem?id=3696
Solution
\(x\) 个 \(8\) 连在一起组成的正整数可以写成 \(8*(10^x-1)/9\) . 题目要求一个最小的 \(x\) 满足 \(L|8*(10^x-1)/9\) .
设 \(gcd(8,L)=d\) , 则 \(\frac{L}{d}|\frac{8}{d}(10^x-1)/9\) . 由于 \(\frac{L}{8}\) 与 \(\frac{8}{d}\) 互质, 所以 \(\frac{L}{d}|(10^x-1)/9\) . 整理得到 \(\frac{9L}{d}|10^x-1\) . 写成同余的形式 \(10^x\equiv 1\ (mod\ \frac{9L}{d})\) .
写到这里我们想到欧拉定理的形式.
对于 \(gcd(10,\frac{9L}{d})!=1\) , 方程无解.
证明: 以上方程等价于 \(10^x=m*\frac{9L}{d}+1\) , 所以 \(gcd(10^x,\frac{9l}{d})=gcd(m*\frac{9l}{d}+1,\frac{9l}{d})=gcd(1,\frac{9l}{d})=1\) .
若 \(a,n\) 互质, 则满足 \(a^x\equiv 1\ (mod\ n)\) 的最小正整数解 \(x_0\) 一定是 \(\varphi(n)\) 的约数.
证明: 假设 \(x_0\not|\ \varphi(n)\) , 则 \(\varphi(n)=m*x_0+r\ (0<r<x_0)\) . 因为 \(a^{\varphi(n)}\equiv 1\ (mod\ n)\) , 那么 \(a^{m*x_0+r}\equiv 1\ (mod\ n)\) . 因为 \(a^{x_0}\equiv 1\ (mod\ n)\) , 那么对上式化简得 \(a^r\equiv 1\ (mod\ n)\) . 这与 \(x_0\) 最小矛盾, 假设不成立. 原命题成立.
因此我们只需要求出 \(\varphi(\frac{9l}{d})\) , 然后枚举它的约数, 用快速幂判断即可.
时间复杂度: \(o(\sqrt{L}\ log\ L)\) .
- Code
- #include<set>
- #include<map>
- #include<cmath>
- #include<queue>
- #include<cstring>
- #include<stdio.h>
- #include<iostream>
- #include<algorithm>
- #define del(a,i) memset(a,i,sizeof(a))
- #define ll long long
- #define inl inline
- #define il inl void
- #define it inl int
- #define ill inl ll
- #define re register
- #define ri re int
- #define rl re ll
- #define mid ((l+r)>>1)
- #define lowbit(x) (x&(-x))
- #define INF 0x3f3f3f3f
- using namespace std;
- template<class T>il read(T &x){
- int f=1;char k=getchar();x=0;
- for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
- for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
- x*=f;
- }
- template<class T>il print(T x){
- if(x/10) print(x/10);
- putchar(x%10+'0');
- }
- ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
- ill qpow(ll x,ll m,ll mod){
- ll res=1,bas=x%mod;
- while(m){
- if(m&1) res=mul(res,bas,mod);
- bas=mul(bas,bas,mod),m>>=1;
- }
- return res%mod;
- }
- ll n,cnt;
- ill gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
- ill phi(ll x){
- rl res=x;
- for(ri i=2;i*i<=x;++i)
- if(x%i==0){
- res=res/i*(i-1);
- while(x%i==0) x/=i;
- }
- if(x>1) res=res/x*(x-1);
- return res;
- }
- il solve(ll n){
- rl d=gcd(8,n);
- rl tmp=9*n/d;
- if(gcd(tmp,10)!=1) printf("Case %lld: 0\n",++cnt);
- else{
- rl p=phi(tmp);
- for(ri i=1;i<=sqrt(p);++i)
- if(p%i==0&&qpow(10,i,tmp)==1){
- printf("Case %lld: %d\n",++cnt,i);
- return ;
- }
- for(ri i=sqrt(p);i>1;--i)
- if(p%i==0&&qpow(10,p/i,tmp)==1){
- printf("Case %lld: %d\n",++cnt,p/i);
- return ;
- }
- }
- }
- int main()
- {
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- while(scanf("%lld",&n)!=EOF){
- if(!n) return 0;
- solve(n);
- }
- return 0;
- }
拓展欧几里得算法
Bezout 定理
? 对于任意整数 \(a,b\) , 一定存在一对整数 \(x,y\) 满足 \(ax+by=gcd(a,b)\) .
证明:
? 在欧几里得算法的最后一步, 即 \(b=0\) 时, 显然有一对整数 \(x=1,y=0\) , 使得 \(a*1+0*0=gcd(a,0)\) .
? 若 \(b>0\) , 则 \(gcd(a,b)=gcd(b,a\%b)\) .
? 假设存在一对整数 \(x,y\) , 满足 \(b*x+(a\%b)*y=gcd(b,a\%b)\) .
? 因为 \(bx+(a\%b)y=bx+(a-b\lfloor a/b\rfloor)y=ay+b(x-\lfloor a/b\rfloor y)\) , 所以令 \(x^{'}=y,y^{'}=x-\lfloor a/b\rfloor y\) , 就得到了 \(ax^{'}+by^{'}=gcd(a,b)\) .
? 对欧几里得算法的递归过程应用数学归纳法, 可知定理成立.
Bezout 定理是按照欧几里得算法的思路证明的, 且上述证明的同时给出了整数 \(x,y\) 的计算方法. 这种计算方法被称作拓展欧几里得算法.
- int exgcd(int a,int b,int &x,int &y){
- if(b==0){x=1,y=0;return a;}
- int d=exgcd(b,a%b,x,y);
- int z=x;x=y,y=z-y*(a/b);
- return d;
- }
上述程序求出方程 \(ax+by=gcd(a,b)\) 的一组特解 \(x_0,y_0\) , 并返回 \(a,b\) 的最大公约数 \(d\) .
对于更一般的方程 \(ax+by=c\) , 它有解当且仅当 \(d|c,d=gcd(a,b)\) . 我们可以先求出 \(ax+by=d\) 的一组特解 \(x_0,y_0\) , 然后令 \(x_0,y_0\) 同时乘上 \(\frac{c}{d}\) , 就得到了 \(ax+by=c\) 的一组特解 \(\frac{c}{d}x_0,\frac{c}{d}y_0\) .
事实上, 方程 \(ax+by=c\) 的通解可以表示为: \(x=\frac{c}{d}x_0+k\frac{b}{d},y=\frac{c}{d}y_0+k\frac{a}{d},k\in\N\) .
例题
题面
题面 https://www.luogu.org/problem/P1516
Solution
假设要跳 \(x\) 次才能相遇, 则题目等价于求一个最小的 \(x\) , 使得 \(a+nx\equiv b+mx\ (mod\ L)\) .
整理式子.
\((n-m)x\equiv b-a\ (mod\ L)\)
将同余号去掉, 得 \(x(n-m)+kL=b-a\) . 其中 \(n-m,L,b-a\) 均为已知量, 所以可以用 \(exgcd\) 求解.
注意到 \(n-m\) 的符号不确定, 所以在做题之前进行一下处理, 先将 \(n-m\) 变为正数, 再将 \(b-a\) 变为正数, 最后再转换为二元一次方程求解.(注意要开 \(long\ long\) )
- Code
- #include<bits/stdc++.h>
- #define del(a,i) memset(a,i,sizeof(a))
- #define ll long long
- #define inl inline
- #define il inl void
- #define it inl int
- #define ill inl ll
- #define re register
- #define ri re int
- #define rl re ll
- #define mid ((l+r)>>1)
- #define lowbit(x) (x&(-x))
- #define INF 0x3f3f3f3f
- using namespace std;
- template<class T>il read(T &x){
- int f=1;char k=getchar();x=0;
- for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
- for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
- x*=f;
- }
- template<class T>il print(T x){
- if(x/10) print(x/10);
- putchar(x%10+'0');
- }
- ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
- it qpow(int x,int m,int mod){
- int res=1,bas=x%mod;
- while(m){
- if(m&1) res=(res*bas)%mod;
- bas=(bas*bas)%mod,m>>=1;
- }
- return res%mod;
- }
- ll a,b,c,n,m,l,x,y;
- ill gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
- ill exgcd(ll a,ll b,ll &x,ll &y){
- if(!b){x=1,y=0;return a;}
- rl d=exgcd(b,a%b,x,y);
- rl z=x;x=y,y=z-(a/b)*y;
- return d;
- }
- int main()
- {
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- read(a),read(b),read(n),read(m),read(l);
- c=b-a,a=n-m,b=l;
- if(a<0) a=-a,c=-c,c=(c%l+l)%l;
- rl d=gcd(a,b);
- if(c%d!=0) printf("Impossible");
- else{
- exgcd(a,b,x,y);
- x=1ll*x*c/d;ri mod=b/d;
- printf("%lld",(x%mod+mod)%mod);
- }
- return 0;
- }
乘法逆元
若整数 \(b,m\) 互质, 并且 \(b|a\) , 则存在一个整数 \(x\) , 使得 \(a/b\equiv a*x\ (mod\ m)\) . 称 \(x\) 为 \(b\) 的模 \(m\) 的乘法逆元. 记为 \(b^{-1}(mod\ m)\) .
因为 \(a/b\equiv a*b^{-1}\equiv a/b*b*b^{-1}(mod\ m)\) , 所以 \(b*b^{-1}\equiv 1(mod\ m)\) .
如果 \(m\) 为质数 (此时用 \(p\) 代替 \(m\) ), 并且 \(b<p\) , 根据费马小定理, \(b^{p-1}\equiv1(mod\ p)\) , 即 \(b*b^{p-2}\equiv1(mod\ p)\) . 因此, 当模数 \(p\) 为质数时, \(b^{p-2}\) 即为 \(b\) 的乘法逆元.
如果只是保证 \(b,m\) 互质, 那么乘法逆元可通过求解同余方程 \(b*x\equiv 1(mod\ m)\) 得到
运用乘法逆元, 我们在计数类问题中遇到 \(a/b\) 这样的除法算式, 也可以先把 \(a,b\) 各自对模数 \(p\) 取模, 再计算 \(a*b^{-1}(mod\ p)\) 作为最终结果. 当然, 前提是必须保证 \(b,p\) 互质.
线性同余方程
给定正数 \(a,b,m\) , 求一个整数 \(x\) 满足 \(a*x\equiv b(mod\ m)\) , 或者给出无解. 因为未知数的指数为 \(1\) , 所以我们称之为一次同余方程, 也称为线性同余方程.
\(a*x\equiv b(mod\ m)\) 等价于 \(a*x-b\) 是 \(m\) 的倍数, 不放设为 \(-y\) 倍. 于是该方程可以改写为 \(a*x+m*y=b\) .
线性同余方程有解当且仅当 \(gcd(a,m)|b\) .
中国剩余定理
设 \(m_1,m_2,\cdots,m_n\) 是两两互质的整数, \(m=\prod\limits_{i=1}^n m_i\) , \(M_i=m/m_i\) , \(t_i\) 是线性同余方程 \(M_it_i\equiv 1(mod\ m_i)\) 的一个解. 对于任意的 \(n\) 个整数 \(a_1,a_2,\cdots,a_n\) , 方程组 \(\left\{\begin{matrix} x\equiv a_1(mod\ m_1)\\ x\equiv a_2(mod\ m_2)\\ \cdots\\ x\equiv a_2(mod\ m_3)\\ \end{matrix}\right.\) 有整数解, 解为 \(x=\sum\limits_{i=1}^n a_i M_i t_i\) .
证明:
? 因为 \(M_i=M/m_i\) , 是除 \(m_i\) 外所有模数的倍数, 所以 \(\forall k\not= i,a_i M_i t_i\equiv 0(mod\ m_k)\) . 又因为 \(a_iM_it_i\equiv a_i(mod\ m_i)\) , 所以带入 \(x=\sum\limits_{i=1}^n a_i M_i t_i\) , 原方程组成立.
来源: http://www.bubuko.com/infodetail-3167243.html