欧拉函数
定义与性质
一个数的欧拉函数被定义为小于等于\(^{①}\)该数的与该数互质的数的个数，记作 \(\varphi(n)\)，这是一个积性函数\(^②\)。
计算
根据定义，可以得出 \(\varphi(n)\) 的计算式：
直接按计算式计算的时间复杂度为 \(O(n\log n)\)，考虑优化：
从上式可以看出 \(\varphi\) 是 \(\mu\) 与 \(\text{id}\) 的狄利克雷卷积\(^③\)，按此计算式使用整除分块\(^④\)计算做到可以 \(O(n)\) 预处理，\(O(\sqrt n)\) 查询，依然不够优秀。
考虑从基本定义出发，设 \(n\) 的唯一分解为 \(\prod\limits_{i=1}^kp_i^{\alpha_i}\)。由 \(\varphi\) 的积性易知：
故只需要在对 \(n\) 分解质因数时计算 \(\varphi\) 即可，时间复杂度为 \(O(\sqrt n)\)。
void get_phi(int x){
int res=x;
for(int 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;
}
线性筛
- 当需要求出 \(1\sim n\) 中每个数的欧拉函数时，可以使用线性筛：
注意到在线性筛中，每一个合数都是被最小的质因子筛掉。比如设 \(p_1\) 是 \(n\) 的最小质因子，\(n' = \frac{n}{p_1}\)，那么线性筛的过程中 \(n\) 通过 \(n' \times p_1\) 筛掉。
观察线性筛的过程，我们还需要处理两个部分，下面对 \(n' \bmod p_1\) 分情况讨论。
如果 \(n'\bmod p_1=0\)，那么 \(n'\) 一定包含了 \(n\) 的所有质因子，即二者唯一分解的 \(p_i\) 均相同。
那如果 \(n' \bmod p_1 \neq 0\) 呢，这时 \(n'\) 和 \(p_1\) 是互质的，根据欧拉函数的积性，我们有：
void sieve(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!v[i]){prime[++cnt]=i;phi[i]=i-1;}
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
v[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
注解
①：考虑 \(\varphi(1)=1\)。
②：若数论函数 \(f\) 对于任意满足 \(\gcd(x,y)=1\) 的正整数 \(x,y\) 均有 \(f(xy)=f(x)f(y)\)，那么我们称 \(f\) 是一个积性函数。
③：两个数论函数 \(f,g\) 的狄利克雷卷积被定义为 \(\sum_{d|n}f(d)g(\big\lfloor\frac{n}{d}\big\rfloor)\)，这是基础数论Ⅲ的内容。
④：通过将 \(\big\lfloor\frac{n}{i}\big\rfloor\) 相同的数打包同时计算的方式降低复杂度，这是基础数论Ⅲ的内容。
⑤：对于任意质数 \(p\)，均有 \(\varphi(p^k)=p^{k-1}(p-1)\)，这是因为在 \(1\sim p^k\) 中，除了 \(p^{k-1}\) 个 \(p\) 的倍数外其他数均与 \(p^k\) 互质，故 \(\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)\)。
裴蜀定理
内容
对于整数 \(a,b\)，一定存在整数 \(x,y\) 使得 \(ax+by=\gcd(a,b)\)。
证明
当 \(a=0,b=0\) 时，结论显然成立。
当 \(a,b\) 中至少一个不为 \(0\) 时，设集合 \(A=\{ax+by \mid x,y\in Z\}\)，即所有能被 \(a,b\) 线性表示出的数的集合。
设 \(d\) 为 \(A\) 中的最小正数，则对于任意 \(x\in A\)，均有 \(d\mid x\)。否则 \(x\bmod d\) 一定可以被 \(a,b\) 线性表示出\(^①\)，即 \(x\bmod d\in A\)，且 \(0<x\bmod d<d\)，与 \(d\) 的定义矛盾。
考虑到 \(a,b\in A\)，故 \(d\mid a,d\mid b\)，即 \(d\) 是 \(a,b\) 的公因子。考虑 \(a,b\) 的任意公因子 \(c\)，有 \(c\mid a,c\mid b\)，故对于任意 \(x\in A\)，均有 \(c\mid x^②\)，即 \(c\mid d\)。故 \(d\) 是 \(a,b\) 的最大公因子。
综上，\(d=\gcd(a,b)\in A\)，即 \(\gcd(a,b)\) 可以被 \(a,b\) 线性表示出，故原命题得证。
推广与结论
不定方程 \(ax+by=c\) 有解的充要条件是 \(\gcd(a,b)\mid c\)，这是裴蜀定理的另一种形式。
裴蜀定理可以被推广到多个数的情况，即对于整数 \(a_1,a_2,\dots ,a_n\)，存在整数 \(b_1,b_2,\dots,b_n\)，使得 \(\sum\limits_{i=1}^na_ib_i=\gcd(a_1,a_2,\dots,a_n)\)。
注解
①：\(x\bmod d\) 可以被 \(x,d\) 线性表示，故也可以被 \(a,b\) 线性表示。
②：\(x\) 可以被 \(a,b\) 线性表示，\(c\mid a,c\mid b\implies c\mid x\)。
费马小定理
内容
若 \(p\) 是质数，则 \(a^{p-1}\equiv 1 \pmod p\)。
其他等价形式：若 \(p\) 是质数，则 \(a^p\equiv a \pod p\)。
证明
考虑数学归纳法，首先当 \(a=1\) 时结论显然成立。
假设当 \(a=k\) 时结论成立，则当 \(a=k+1\) 时根据二项式定理有
容易发现 \(C_p^{i}\) 在 \(0<i<p\) 时均有 \(C_{p}^i\equiv 0 \pmod p\)，故 \((k+1)^p\equiv k^p+1\pmod p\)，将 \(k^p\equiv k\pmod p\) 代入得 \((k+1)^p\equiv k+1 \pmod p\)，故当 \(a=k+1\) 时结论成立。
由数学归纳法易知对于任意正整数 \(a\) 结论均成立。
欧拉定理
内容
若 \(\gcd(a,p)=1\)，则 \(a^{\varphi(p)}\equiv 1\pmod p\)
证明
设 \(q_1,q_2,\dots,q_{\varphi(p)}\) 为模 \(p\) 意义下的一个简化剩余系\(^①\)，则 \(aq_1,aq_2,\dots,aq_{\varphi(p)}\) 也是模 \(p\) 意义下的一个简化剩余系，故 \(\prod\limits_{i=1}^{\varphi(p)}q_{i}\equiv \prod\limits_{i=1}^{\varphi(p)}aq_i\pmod p\)，即 \(a^{\varphi(p)}\equiv 1\pmod p\)。
扩展欧拉定理
- 形式：
证明较为复杂，此处略去。
注解
①：在与模 \(m\) 互质的的全部剩余类\(^②\)中每类任取一数构成的数的集合叫做模 \(m\) 的一个简化剩余系。
②：按照模 \(m\) 的值将所有整数分成 \(m\) 类，每一类叫做模 \(m\) 的一个剩余类。
扩展欧几里得算法
作用
扩展欧几里得算法可以求出不定方程 \(ax+by=\gcd(a,b)\) 的一组解。
过程与实现
设：
由欧几里得定理可知：\(\gcd(a,b)=\gcd(b,a\bmod b)\)。
故 \(ax_1+by_1=bx_2+(a\bmod b)y_2=bx_2+(a-b\lfloor\frac{a}{b}\rfloor)y_2=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)\)。
对比系数易知 \(x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2\)，\(x_2,y_2\) 可以迭代求解。
终止条件：\(b=0\) 时 \(x=1,y=0\)。
void exgcd(int a,int b,int &x,int &y){
if(!b){x=1;y=0;return a;}
int d=exgcd(a,b,x,y);
int z=x;x=y;y=z-(a/b)*y;
return d;
}
乘法逆元
定义
对于整数 \(a\)，如果存在整数 \(x\)，使得 \(ax\equiv 1\pmod b\)，则称 \(x\) 是 \(a\bmod b\) 的逆元，记作 \(a^{-1}\)。
逆元可以被理解为模意义下的倒数。
快速幂求法
根据费马小定理，\(a^{p-1}\equiv 1\pmod p\)，则 \(a\times a^{p-2}\equiv 1\pmod p\)，故当模数是质数时，\(a\) 的一个逆元为 \(a^{p-2}\)。
扩展欧几里得求法
将 \(ax\equiv 1\pmod b\) 改写为 \(ax+by=1\)，就可以使用扩展欧几里得算法求解。
void inv(int a,int p){
int x=0,y=0;
exgcd(a,p,x,y);
return (x%p+p)%p;
}
线性求法
当需要求出 \(n\) 个数逆元时，可以使用下列方法求解。
首先计算 \(n\) 个数的前缀积，记为 \(s_i\)，然后使用快速幂或扩展欧几里得法计算 \(s_n\) 的逆元，记为 \(sv_n\)。
因为 \(sv_n\) 是 \(n\) 个数的积的逆元，所以当我们把它乘上 \(a_n\) 时，就会和 \(a_n\) 的逆元抵消，于是就得到了 \(a_1\) 到 \(a_{n-1}\) 的积逆元，记为 \(sv_{n-1}\)。
同理我们可以依次计算出所有的 \(sv_i\)，于是 \(a_i^{-1}\) 就可以用 \(s_{i-1}\times sv_i\) 求得。
所以我们就在 \(O(n+\log p)\) 的时间内计算出了 \(n\) 个数的逆元。
void init(){
s[0]=1;
for(int i=1;i<=n;i++) s[i]=s[i-1]*a[i]%p;
sv[n]=inv(s[n],p);
for(int i=n;i>=1;i--) sv[i-1]=sv[i]*a[i]%p;
for(int i=1;i<=n;i++) inv[i]=sv[i]*s[i-1]%p;
}
这种方法常用于预处理组合数，即预处理阶乘和阶乘逆元。
线性同余方程
定义
形如
的方程被称为线性同余方程。
逆元求法
当 \(\gcd(a,p)=1\) 时，有解 \(x\equiv ba^{-1}\pmod p\)。
当 \(\gcd(a,p)\not =1\) 时，若 \(\gcd(a,p)\not \mid b\) 则方程无解，否则 \(a,b,p\) 同除 \(\gcd(a,p)\) 转化为 \(\gcd(a,p)=1\) 的情况。
扩展欧几里得求法
将方程改写为 \(ax+py=b\) 的形式，由裴蜀定理得有解的充要条件为 \(\gcd(a,p)\mid b\)，此时用扩展欧几里得算法求出 \(ax+py=\gcd(a,p)\) 的一组解，再同乘 \(\frac{b}{\gcd(a,p)}\) 就得到了原方程的一组解。
bool calc(int a,int b,int p,int &x,int &y){
int d=exgcd(a,p,x,y);
if(b%d) return 0;
x*=b/d;y*=b/d;
return 1;
}