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$ 为合数」会导致有些时候不存在逆元。
如果正好存在逆元也是可以继续做的。
原理：
注意空间复杂度为 $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(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}$ ，即费马小定理
扩展欧拉定理
应用
例题：
求
$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$ ，有
$\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)可求解如下形式的一元线性同余方程组
其中 $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}$ 。
可得
因此
令 $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$ ，则
为一组通解。于是我们求最小的解 $u_0 \equiv u_1 \cdot \frac{c}{g} \pmod{\frac{p_2}{g}}$ ，钦定 $u_0 > 0$ （都是为了方便和防止溢出）。
那么原方程就可以写作
这样我们就合并了两个式子，依此类推可以解决所有的式子。
时间复杂度 $\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$ 为莫比乌斯函数，定义为
代码求解
线性筛 $\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; }
}
}
}莫比乌斯反演
应用
一个小转化（仅改变这两个相关和式，左侧其他的 $\Sigma$ 不变）
设 $d(x)$为 $x$ 的约数个数，则有
拉格朗日定理
设 $p$ 为素数，对于模 $p$ 意义下的整系数多项式
的同余方程 $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$ ，则
的充分必要条件是
设 $k\in \mathbb{N},m\in \mathbb{N}^*,a\in\mathbb{Z} ,\gcd(a,m)=1$ ，则
原根：设 $m\in \mathbb{N}^*,a \in \mathbb{Z} $ 若 $\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）
Legendre 符号为完全积性函数
Euler 判别准则
对于奇素数
引理：令 $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\in \mathbb{Z} $ ，$x^d \equiv 1 \pmod{p}$ 恰有 $d$ 个解
参考文献：
