本文主要记录自己学习 OI 时用到的数论知识，内容偏进阶。
因为近期其实不太会用到多么高深的数论知识，所以很多内容是空中楼阁，是照抄 OI Wiki 而缺乏自己的理解，这些都等需要的时候慢慢补。这次写笔记主要在于建立起知识体系，知道有哪些东西要掌握。
那么开始。
数论分块
基本的思想是集合 \(\{\lfloor \frac{n}{i} \rfloor | i=1,2,\cdots n\}\) 的元素个数不超过 \(2 \sqrt n\)，所以在计算形如 \(\sum_{i=1}^{n} f(i)g(\lfloor \frac{n}{i} \rfloor)\) 的和式时，可以固定 \(\lfloor \frac{n}{i} \rfloor\)，快速计算 \(f\) 的前缀和来处理。
代码：
for(int l=1,r=0;l<=n;l=r+1){
r=n/(n/l);
//计算
l=r+1;
}
费马小定理&欧拉定理
\(a^p \ equiv a \pmod n\) 在 \(p\) 时素数时成立。
\(a^{\varphi(n)} \equiv 1 \pmod n\) 在 \((a,n)=1\) 时成立。
\(a^m \equiv a^{m \bmod \varphi(n)+\varphi(n)}\) 在 \(m \ge \varphi(n)\) 时成立。
模板题：求 \(a^b \bmod m\)。\(1\le a \le 10^9\)，\(1\le b \le 10^{20000000}，1\le m \le 10^8\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e7+5;
int a,m,k,n,flag;char ch;
int phi(int m){
int res=m;
for(int i=2;i*i<=m;i++)
if(m%i==0){
res=res/i*(i-1);
while(m%i==0)m/=i;
}
if(m!=1)res=res/m*(m-1);
return res;
}
int power(int a,int b,int P){
int c=1;
for(;b;b>>=1){
if(b&1)c=1ll*c*a%P;
a=1ll*a*a%P;
}
return c;
}
int main(){
scanf("%d%d",&a,&m);
n=phi(m);
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){
k=(k<<1)+(k<<3)+(ch^48);
if(k>=n)k%=n,flag=1;
ch=getchar();
}
printf("%d\n",power(a%m,k+flag*n,m));
return 0;
}
扩展欧几里得
放个模板题代码就行了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,x,y;
ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){x=1;y=0;return a;}
ll d=exgcd(b,a%b,x,y);
ll z=x;x=y;y=z-y*(a/b);
return d;
}
int main(){
a=read();b=read();
exgcd(a,b,x,y);
printf("%lld\n",(x%b+b)%b);
return 0;
}
中国剩余定理
模板题和代码。思路是每次把两个合并为一个。
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int N=1e5+5;
int n;ll a,b,m,p,x,y,d,ans;long long m0,p0,a0,b0;
void exgcd(ll a,ll b,ll&x,ll&y,ll&d){
if(b==0){x=1;y=0;d=a;return;}
exgcd(b,a%b,x,y,d);ll x0=x,y0=y;
x=y0;y=x0-a/b*y0;
}
int main(){
scanf("%d",&n);
scanf("%lld%lld",&m0,&p0);
m=m0;p=p0;
for(int i=2;i<=n;++i){
scanf("%lld%lld",&a0,&b0);
a=a0;b=b0;
exgcd(m,a,x,y,d);
a/=d;ll m0=m/d;m*=a;
x=(x%m+m)%m;y=(y%m+m)%m;
p=(p*a%m*y%m+b*m0%m*x%m)%m;
}
p0=p;
printf("%lld\n",p0);
return 0;
}
Lucas定理
若 \(p\) 为素数，则
可以用来求一个组合数模素数的值。只要在 \(p\) 进制下求每一位的对应组合数乘起来。
若模数不一定为素数，可以用质因数分解后用中国剩余定理处理。对于 \(p^a\) 的形式，先用勒让德公式 \(v_p(n!)=\sum_{i=1}^{\infty}\lfloor \frac{n}{p^i} \rfloor\) 结合组合数定义算出 \(p\) 的幂次即可。
模板题，代码待补。
离散对数
数学中不讲的东西。
定义：设 \(g\) 为模 \(n\) 的原根，\(g^t \equiv a \pmod n\)，则 \(t\) 为 \(a \bmod n\) 的离散对数，\(t \bmod \varphi(n)\) 为 \(a\bmod n\) 离散对数的主值。
算法：BSGS 算法。（大步小步/北上广深）
问题：在 \((a,p)=1\) 的条件下，求解同余方程 \(a^x \equiv b \pmod p\)。
时间复杂度： \(O(\sqrt p)\)
思路：设解 \(x=AN-B\)，\(N\) 待定，\(0\le B \lt N\)。则化为 \((a^N)^A \equiv ba^B \pmod p\)。枚举 \(B\)，用哈希表存下来，然后枚举 \(A\) 判断即可。
模板题，代码待补。
扩展：如果\((a,p) \ne 1\)，不断从 \(a^x\) 中提出一个 \(a\)，约去公因数，直到两边互素即可。
莫比乌斯反演
莫比乌斯函数 \(\mu (n)\) 定义为：若 \(n\) 有素因子幂次大于 \(1\)，则 \(\mu (n)=0\)；否则 \(\mu(n)=(-1)^k\)，其中 \(k\) 为 \(n\) 的不同素因子个数。
性质：\(\sum_{d|n}\mu (d)= [n==1]\)，有时也记 \(\varepsilon(n)=[n==1]\)。
狄利克雷卷积：\(f \ast g = h\) 表示 \(h(n)=\sum_{d|n}f(d)g(\frac{n}{d})\)。
莫比乌斯反演：\(f\ast 1=g \iff g \ast \mu =f\)。
杜教筛
问题：求函数 \(f\) 的前缀和 \(S\)。
时间复杂度：\(O(n^{\frac{2}{3}})\)
思想：利用狄利克雷卷积构造 \(S(n)\) 关于 \(S(\lfloor \frac{n}{i} \rfloor)\) 的递推式。具体地，
则 \(g(1)S(n)=\sum_{i=1}^{n} (f\ast g)(i)-\sum_{i=2}^{n}g(i)S(\lfloor \frac{n}{i} \rfloor)\)
只要能快速处理 \(f\ast g\) 的前缀和，以及 \(g\) 的前缀和，然后递归处理。
这时的时间复杂度还是 \(O(n^{\frac{3}{4}})\)。
然后，对于 \(m \le n^{\frac{2}{3}}\)，用某些方法预处理 \(S(m)\)，再递归处理是的复杂度就成为 \(O(n^{\frac{2}{3}})\)。
模板题，代码待补。
例题，题解参看Competition Set - 在线赛中 HDU多校赛 第二场 的 1002 题。