OI数学总结-数论
注意，本文不同于 OI模板-数学
本文倾向于数学概念，但是包含部分代码，只是因为数论的内容与代码联系紧密，因此显得较为相似。
积性函数
数论中定义：定义域为正整数域的函数 \(f(n)\) ，
且满足 \(\forall a,b \in \mathbb{Z} _+,f(ab)=f(a)f(b) \land \gcd(a,b)=1\)
完全积性函数
数论中定义：定义域为正整数域的函数 \(f(n)\) ，
且满足 \(\forall a,b \in \mathbb{Z} _+,f(ab)=f(a)f(b)\)
最大公约数 gcd
最大公约数指能够整除多个不全为零的整数的最大正整数
常用性质： \(a\times b = \gcd(a,b) \times \mathrm{lcm}(a,b)\)
代码求解
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
} // 注意这份代码对于(+,-)的情况会求出负数裴蜀定理
设 \(a,b\) 是不全为零的整数，则存在整数，使得 \(ax+by=\gcd(a,b)\)
证明详见 裴蜀定理及其证明
扩展欧几里德算法(Exgcd)
板子题： P5656 【模板】二元一次不定方程 (exgcd)
若 \(b \ne 0\) ，扩展欧几里得算法求出的可行解必有 \(|x| \le b ,|y| \le a\) 。
int exgcd(int a,int b,int &x,int &y)
{
int d=a;
if(!b)x=1,y=0;
else d=exgcd(b,a%b,y,x),y-=a/b*x;
return d;
}
void solve()
{
int a,b,c,x,y;
read(a);read(b);read(c);
int d=exgcd(a,b,x,y);
if(c%d!=0){puts("-1");return;} // 无解
x*=c/d;y*=c/d;
int p=b/d,q=a/d,k;
if(x<0)k=ceil((1.0-x)/p),x+=p*k,y-=q*k; // 将x提高到最小正整数
else k=(x-1)/p,x-=p*k,y+=q*k; // 将x降低到最小正整数
if(y>0) // 存在x>0,y>0的解（正整数）
{
write((y-1)/q+1); pc(' '); // 将y减到1的方案数即为解的个数
write(x); pc(' '); // 当前的x为最小正整数
write((y-1)%q+1); pc(' '); // 将y取到最小正整数
write(x+(y-1)/q*p); pc(' '); // 将x提升到最大
write(y); pc(' '); // 特解即为y的最大值
}else // 仅存在整数解
{
write(x); pc(' '); // 当前的x
write(y+q*(int)ceil((1.0-y)/q));pc(' '); // 将y提高到正整数
}
pc('\n');
}费马小定理
若 \(p\) 为素数 ， \(\gcd(a,p)=1\) 则 \(a^{p-1}\equiv 1 \pmod{p}\)
若 \(p\) 为素数 ，则对于任意整数 \(a\) ，有 \(a^p \equiv a \pmod{p}\)
常用于 \(O(\log n)\) 求解 \(n\) 模素数 \(p\) 意义下的逆元，详见逆元部分。
逆元
如果一个线性同余方程组 \(ax \equiv 1 \pmod{b}\) ，则 \(x\) 称为 \(a \bmod b\) 的逆元，记作 \(a^{-1}\)
模意义下的乘法逆元不唯一。
如果 \(b\) 不为素数，可能不存在逆元。
代码求解
\(O(n)\) 预处理 ，\(O(1)\) 查询
求的是 \(1,2,\cdots ,n\) 的模 \(p\) 意义下的乘法逆元，\(p\) 一般为质数。
为什么说一般呢？因为「 \(p\) 为合数」会导致有些时候不存在逆元。
如果正好存在逆元也是可以继续做的。
原理： \[ \begin{aligned} i^{-1} &\equiv \begin{cases} 1,&\text{if }i=1,\\\\ -\left\lfloor\dfrac{p}{i}\right\rfloor \left(p\bmod{i}\right)^{-1}, &\text{otherwises.} \end{cases} \pmod{p} \end{aligned} \]
注意空间复杂度为 \(O(n)\)
inv[1]=1;
for(int i=2; i<=n; i++)
inv[i]=(p-p/i)*inv[p%i]%p;费马小定理 \(O(\log p)\) 查询 \(x\) 的逆元
原理：\(x \equiv a^{p-2}\pmod{p}\) （根据费马小定理）
\(p\) 需要是质数
cout << qpow(a,p-2) << '\n'; // 快速幂\(\text{Exgcd}~O(\log p)\) 查询 \(x^{-1}\)
求的是 \(a\) 在模 \(p\) 意义下的逆元，要求模数 \(p\) 与 \(a\) 互质。
int exgcd(int a,int b,int &x,int &y)
{
int d=a;
if(!b)x=1,y=0;
else d=exgcd(b,a%b,y,x),y-=a/b*x;
return d;
}
int solve(int a,int p)
{
int x,y;
exgcd(a,p,x,y);
x=(x%p+p)%p;
return x;
}\(\mathcal{O}(n)\) 预处理阶乘的逆元
因为 \(n!=(n-1)! \times n\) ，所以 \(((n-1)!)^{-1}=(n!)^{-1} \times n\) 。模数 \(p\) 为质数。
for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % p;
invf[n] = qpow(fac[n], p-2); // 费马小定理
for(int i=n-1; i>=1; i--) invf[i] = invf[i+1] * (i+1) % p;请注意，如果 \(p \le n\) ，这种方法就不可行了，因为 \(n! \bmod p =0\) ，会出现不存在逆元的情况
这种时候一般采用上文线性求逆元的方法，只要求 \(1\sim p-1\) 的就行了，即
// luogu P2675
for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % p;
for(int i=2; i<p; i++) inv[i] = (p-p/i) * inv[p%i] % p; // 注意是1 ~ p-1欧拉函数
欧拉函数 \(\varphi(n)\) 表示小于等于 \(n\) 和 \(n\) 互质的数的个数。
设 \(n=\prod_{i=1}^{s}p_i^{k_i}\) \[ \varphi(n) = n \prod\limits_{i=1}^s\left(\dfrac{p_i-1}{p_i}\right) = \prod(p_i-1)\times p_i^{k_i-1} \]
常用性质：\(\varphi(1) = 1,~\varphi(p) = p-1,~p\in\mathbb{P}\) ，以及 \(n > 2\) 时，\(\varphi(n)\) 为偶数
代码求解
\(O(\sqrt{n})\) 求 \(\varphi(n)\)
板子题：poj2407
int Euler_phi(int n)
{
int ans=n;
for(int i=2; i<=n/i; 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;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n;
while(cin>>n&&n!=0)
cout << Euler_phi(n) << endl;
return 0;
}线性筛 \(O(n)\) 求解
poj2478
（这个题要改成 \(\varphi\)
的前缀和）
int phi[N],prime[N],pcnt;
bool ck[N];
void Euler()
{
ck[1]=1;
phi[1]=1;
for(int i=2; i<=N-5; i++)
{
if(!ck[i])
{
prime[++pcnt]=i;
phi[i]=i-1;
}
for(int j=1; j<=pcnt&&i*prime[j]<=N-5; j++)
{
int pos=i*prime[j];
ck[pos]=1;
if(i%prime[j])
{
phi[pos]=phi[i]*phi[prime[j]];
}
else
{
phi[pos]=phi[i]*prime[j];
break;
}
}
}
}欧拉定理
若 \(\gcd(a,m) = 1\) ，则 \(a^{\varphi(m)} \equiv 1\pmod{m}\)
当 \(m\) 为素数时，根据欧拉函数的性质有 \(a^{m-1}\equiv 1 \pmod{m}\) ，即费马小定理
扩展欧拉定理
\[ \begin{aligned} a^b \equiv \begin{cases} a^b,&b< \varphi(m)\\\\ a^{b \ \bmod \ \varphi(m)+\varphi(m)},&b\ge \varphi(m) \end{cases} \pmod{m} \end{aligned} \]
应用
例题：
求 \[
a^b\bmod m
\] \(1\le a,m\le 10^{12},1\le b\le
10^{20000000}\)（这个是加强版的，朴素版只要int就行）
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
int a,m,b,flag;
int Euler_phi(int n)
{
int ans=n;
for(int i=2; i<=n/i; 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;
}
int qpow(int a,int b,int p)
{
int ans=1,base=a%p;
while(b)
{
if(b&1)ans=(__int128)ans*base%p;
base=(__int128)base*base%p;
b>>=1;
}
return ans;
}
signed main()
{
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
scanf("%lld%lld",&a,&m);
a%=m;
int phi=Euler_phi(m);
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))
{
b=(b<<1)+(b<<3)+(ch^48);
if(b>=phi)flag=1,b%=phi;ch=gc();
}
if(b>=phi)flag=1,b%=phi;
if(flag)b+=phi;
printf("%lld\n",qpow(a,b,m));
return 0;
}Lucas定理
对于质数 \(p\) ，有 \[ \dbinom{n}{m} \bmod p = \dbinom{\left\lfloor{n/p}\right\rfloor}{\left\lfloor{m/p}\right\rfloor} \times \dbinom{n \bmod p}{m \bmod p} \bmod p \] \(\binom{\left\lfloor{n/p}\right\rfloor}{\left\lfloor{m/p}\right\rfloor}\) 采用递归处理，后面的直接 \(O(p)\) 预处理组合数
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e5+15)
int Q,n,m,p;
int fac[N];
int qpow(int a,int b,int p)
{
int ans=1,base=a;
while(b)
{
if(b&1)ans=ans*base%p;
base=base*base%p;
b>>=1;
}
return ans;
}
// n 选 m
int C(int n,int m,int p)
{
if(n<m)return 0;
return fac[n]*qpow(fac[m],p-2,p)%p*qpow(fac[n-m],p-2,p)%p;
}
int lucas(int n,int m,int p)
{
if(!m)return 1;
return lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
signed main()
{
cin >> Q;
while(Q--)
{
cin >> n >> m >> p;
fac[1]=fac[0]=1;
for(int i=2; i<=n+m; i++)
fac[i]=fac[i-1]*i%p;
cout << lucas(n+m,m,p) << '\n'; // C(n+m,n)
}
return 0;
}中国剩余定理
参考 中国剩余定理 & 扩展
中国剩余定理(CRT)可求解如下形式的一元线性同余方程组 \[ \begin{cases} x \equiv a_1\ \pmod{p_1} \\[6pt] x\equiv a_2\ \pmod{p_2} \\[6pt] \quad\vdots \\[6pt] x \equiv a_n\ \pmod{p_k}\end{cases} \] 其中 \(p_1,p_2,\cdots,p_k\) 两两互质。
板子题：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪
算法原理很简单
- 计算 \(P = \prod p_i\)
- 记 \(m_i = \frac{P}{p_i}\) ，\(m_i^{-1}\) 为模 \(p_i\) 意义下的乘法逆元，求 \(c_i = m_im_i^{-1}\)
- 方程组的唯一解 \(x = \sum_{i=1}^{k}a_ic_i\pmod{P}\)
证明就不讲了，中国剩余定理主要还是流程比较难记（确信）
时间复杂度 \(\mathcal{O}(n \log V)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(15))
int a[N],p[N];
void exgcd(int a, int b, int &x, int &y)
{
if(!b) { x = 1, y = 0; }
else exgcd(b, a % b, y, x), y -= a / b * x;
}
int solve(int n, int P)
{
int res = 0;
for(int i = 1; i <= n; i++)
{
int m = P / p[i], x, y;
exgcd(m, p[i], x, y); // m * x % p[i] = 1;
res = (res + a[i] * m % P * x % P) % P;
}
return (res % P + P) % P;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n, P = 1; cin >> n;
for(int i = 1; i <= n; i++) {
cin >> p[i] >> a[i]; P = P * p[i];
}
cout << solve(n, P) << '\n';
return 0;
}扩展中国剩余定理
ExCRT 用于解决 \(p_i\) 不一定互质的情况
设两个方程为 \(x \equiv a_1 \pmod{p_1},~x \equiv a_2 \pmod{p_2}\) 。
可得 \[ x = p_1\cdot u +a_1 = p_2\cdot v + a_2 \] 因此 \[ p_1 \cdot u - p_2 \cdot v = a_2 - a_1 \] 令 \(c = (a_2 - a_1)\) 。由裴蜀定理， 当且仅当 \(\gcd(p_1,p_2)\mid c\) 时有解。
于是我们可以通过 exgcd 求出一对 \(u_1,v_1\) ，满足 \(p_1\cdot u_1 + p_2 \cdot v_1=g\) （\(-p_2\) 与此实际上等价）
令 \(g = \gcd(p_1,p_2)\) ，显然 \(p_1u_1 \cdot \frac{c}{g} + p_2v_1 \cdot \frac{c}{g} = c\) ，则 \[ \begin{cases} u = u_1 \cdot \frac{c}{g} + \frac{p_2}{g}\cdot k \\[8pt]v = v_1 \cdot \frac{c}{g} - \frac{p_1}{g}\cdot k \end{cases} \] 为一组通解。于是我们求最小的解 \(u_0 \equiv u_1 \cdot \frac{c}{g} \pmod{\frac{p_2}{g}}\) ，钦定 \(u_0 > 0\) （都是为了方便和防止溢出）。
那么原方程就可以写作 \[ x \equiv p_1 u_0 + a_1 \pmod{\mathrm{lcm}(p_1,p_2)} \] 这样我们就合并了两个式子，依此类推可以解决所有的式子。
时间复杂度 \(\mathcal{O}(n \log V)\)
代码：
// 2024年02月09日 03:38:48
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
int exgcd(int a, int b, int &x, int &y)
{
int d = a;
if(!b) { x = 1, y = 0; }
else { d = exgcd(b, a % b, y, x), y -= a / b * x;}
return d;
}
int a[N], p[N];
int ExCRT(int n)
{
int u, v, p1 = p[1], res = a[1];
for(int i = 2; i <= n; i++)
{
int p2 = p[i], c = (a[i] - res % p2 + p2) % p2;
int g = exgcd(p1, p2, u, v); assert(c % g == 0);
int l = p2 / g; u = (__int128_t) u * (c / g) % l;
res += u * p1; p1 *= l; res = (res % p1 + p1) % p1;
}
return (res % p1 + p1) % p1;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n; cin >> n;
for(int i = 1; i <= n; i++) cin >> p[i] >> a[i];
cout << ExCRT(n) << '\n';
return 0;
}莫比乌斯函数
\(\mu\) 为莫比乌斯函数，定义为 \[ \begin{aligned} \mu(n) = \begin{cases} 1,&n=1\\[8pt] (-1)^k,&k\text{ 为 }n \text{ 本质不同质因子个数}\\[8pt] 0,&n\text{含有平方因子（其实就是剩余的情况）} \end{cases} \end{aligned} \]
代码求解
线性筛 \(\mathcal{O}(n)\) 求 \(\mu\)
// 2023年07月04日 20:43:15
void Mobius(int n = N - 10)
{
mu[1] = 1;
for(int i = 2; i <= n; i++)
{
if(!ck[i]) { prime[++pcnt] = i; mu[i] = -1; }
for(int j = 1; j <= pcnt && i * prime[j] <= n; j++)
{
int pos = i * prime[j]; ck[pos] = true;
if(i % prime[j]) { mu[pos] = -mu[i]; } else { mu[pos] = 0; break; }
}
}
}莫比乌斯反演
\[ \sum_{d\mid \gcd(i,j)}\mu(d)=[\gcd(i,j)=1]=[i\perp j] \]
应用
一个小转化（仅改变这两个相关和式，左侧其他的 \(\Sigma\) 不变） \[ \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k] =\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[\gcd(i,j)=1] \] 设 \(d(x)\)为 \(x\) 的约数个数，则有 \[ d(ij)=\sum_{x\mid i}\sum_{y \mid j}[\gcd(x,y)=1] \]
拉格朗日定理
设 \(p\) 为素数，对于模 \(p\) 意义下的整系数多项式 \[ f(x) = \sum_{n\ge 0}a_nx^n,p\nmid a_n \] 的同余方程 \(f(x) \equiv 0 \pmod{p}\) 在模 \(p\) 意义下至多有 \(n\) 个不同解
应用
关于同余方程的引理：
对于任意 \(a\) ，至多有 \(n\) 个不同的 \(x\) 满足同余方程 \(nx \equiv a \pmod{m}\)
应用于抽象代数的定理中：
在有限可交换群 \(G\) 中，以下两个条件等价：
\(G\) 是循环群。
对于任意一个元素 \(a\) ，至多有 \(n\) 个不同的元素 \(x\) 满足条件 \(x^n=a\) 。
结论：对于素数 \(p\) ，模 \(p\) 的简化剩余系 \(Z_p^*\) 对于乘法构成的群是循环群
原根
阶：满足同余式 \(a^n \equiv 1 \pmod{m}\) 的最小正整数 \(n\) 存在，这个 \(n\) 称作 \(a\) 模 \(m\) 的阶，记作 \(\delta_m(a)\)
在抽象代数中，这里的“阶”就是模 \(m\) 缩剩余系关于乘法形成的群中，元素 \(a\) 的阶。记号 \(\delta\) 表示阶也只用于这个特殊的群。
下面的诸多性质可以直接扩展到抽象代数中阶的性质。
阶的性质
\(a,a^2,\dots,a^{\delta_m(a)}\) 模 \(m\) 两两不同余
若 \(a^n \equiv 1 \pmod{m}\) ，则 \(\delta_m(a) \mid n\)
若 \(a^p \equiv a^q \pmod{m}\) ，则有 \(p\equiv q \pmod{\delta_m(a)}\)
设 \(m \in \mathbb{N}^*，a,b \in \mathbb{Z} ,\gcd(a,m)=\gcd(b,m)=1\) ，则 \[ \delta_m(ab)=\delta_m(a)\delta_m(b) \] 的充分必要条件是 \[ \gcd(\delta_m(a),\delta_m(b))=1 \]
设 \(k\in \mathbb{N},m\in \mathbb{N}^*,a\in\mathbb{Z} ,\gcd(a,m)=1\) ，则 \[ \delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)} \]
原根：设 $m^*,a $ 若 \(\gcd(a,m)=1\) ，且 \(\delta_m(a) = \varphi(m)\) ，则称 \(a\) 为模 \(m\) 的原根
在抽象代数中，原根就是循环群的生成元。这个概念只在模 \(m\) 缩剩余系关于乘法形成的群中有“原根”这个名字，在一般的循环群中都称作“生成元”。
并非每个模 \(m\) 缩剩余系关于乘法形成的群都是循环群，存在原根就表明它同构于循环群，如果不存在原根就表明不同构。
原根判定定理：设 \(m\ge 3，\gcd(a,m)=1\) ，则 \(a\) 是模 \(m\) 的原根的充要条件是，对于 \(\varphi(m)\) 的每个素因数 \(p\) ，都有 \(a^{\frac{\varphi(m)}{p}}\not\equiv 1 \pmod{m}\)
原根个数：若一个数 \(m\) 有原根，则它的原根个数为 \(\varphi(\varphi(m))\)
原根存在定理：一个数 \(m\) 存在原根当且仅当 \(m=2,4,p^\alpha,2p^\alpha\) ，其中 \(p\) 为奇素数，\(\alpha \in \mathbb{N}^*\)
- 定理1：对于奇素数 \(p\) ，\(p\) 有原根
- 定理2：对于奇素数 \(p\) ，\(\alpha \in \mathbb{N}^*\) ，\(p^\alpha\) 有原根
- 定理3：对于奇素数 \(p\) ，\(\alpha\in\mathbb{N}^*\) ，\(2p^\alpha\) 的原根存在
- 定理4：对于 \(m\ne2,4\) ，且不存在奇素数 \(p\) 及 \(\alpha \in \mathbb{N}^*\) 使得 \(m=p^\alpha,2p^\alpha\) ，模 \(m\) 的原根不存在
二次剩余
对于二次同余方程 \(x^2\equiv n \pmod{p}\) 有解，则称 \(n\) 为 \(p\) 的二次剩余，\(x\) 为该二次同余方程的解
二次剩余 \(n\) 就是一个二次项 \(\bmod p\) 后的剩余，\(n\) 不可以是 \(p\) 的倍数
Legendre 符号（中间那个发音是g不是j） \[ \left(\dfrac{a}{p}\right)=\begin{cases} 1,&p\nmid a \text{ 且 }a \text{ 是模 }p \text{ 的二次剩余} , \\-1,&p\nmid a \text{ 且 }a \text{ 不是模 }p \text{ 的二次剩余} , \\0,&p\mid a. \end{cases} \] Legendre 符号为完全积性函数
Euler 判别准则
对于奇素数 \[ a^{\frac{p-1}{2}} \equiv \left(\dfrac{a}{p}\right)\equiv\begin{cases} 1 \pmod{p}, \text{ 若 }x^2 \equiv a \pmod{p} \text{ 有解}, \\\\-1 \pmod{p}, \text{ 若 }x^2 \equiv a \pmod{p} \text{ 无解}. \end{cases} \]
引理：令 \(p\) 为素数和模 \(p\) 意义下原根 \(g\) 并令 \(a\equiv g^k \pmod{p}\) ，那么 \(x^2 \equiv a \pmod{p}\) 有解当且仅当 \(k\) 为偶数
二次剩余和二次非剩余的数量
对于奇素数 \(p\) 和集合 \(\{1,2,\dots,p-1\}\) ，在模 \(p\) 意义下二次剩余的数量等于二次非剩余的数量
引理：对于 \(d \mid (p-1)\) 和奇素数 $p $ ，\(x^d \equiv 1 \pmod{p}\) 恰有 \(d\) 个解
参考文献：
