1.质数和约数
质数：
若一个正整数无法被除了 \(1\) 和它本身之外的任何自然数整除，则称该数为质数。
质数的判定：
-
试除法
-
Miller-Robbin
Eratosthenes筛法
每个合数 \(a\) 一定可以写成 \(p\times x\) 的形式，其中 \(p\) 是素数，\(x\) 是倍数 \((x\neq 1)\)。
对于每个 \(1\) 到 \(n\) 内的素数 \(p\)，枚举倍数 \(x\) 把 \(p\times x\) 标记为合数，这就是埃氏筛法。
筛选时做一个改进：对于素数 \(p\)，只筛倍数 \(x\ge p\) 的数，因为如果 \(x<p\) ,则 \(x\) 中一定有比 \(p\) 小的素因子，\(p\times x\) 会在前面筛选过程中被筛出。
因此只需考虑 \(2\) 到 \(n\) 范围的素数。
时间复杂度：\(O(nloglogn)\)
p[0]=p[1]=true;
for(int i=2;i<=n;i++){
if(p[i])
continue;
for(int j=i;i*j<=n;++j)
p[i*j]=true;
}
线性筛法
在 Eratosthenes 筛法中，合数会被重复标记。
如果每个合数只被它的最小质因数标记，那么每个数最多只会被标记一次。
依次考虑 \(2\) 到 \(n\) 之间的每一个数 \(i\)。
如果 \(i\) 是质数，则将其保存到质数表中。
否则利用 \(i\) 和质数表中的 \(pri[j]\) 筛去 \(i\times pri[j]\)。
筛的过程中要确保 \(pri[j]\) 是 \(i\times pri[j]\) 的最小质因子。
p[0]=p[1]=true;
for(int i=2;i<=n;i++){
if(!p[i])
pri[++cnt]=i;
for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
p[i*pri[j]]=true;
if(!i%pri[j])
break;
}
}
算术基本定理
若整数 \(n \ge 2\)，那么 \(n\) 一定可以唯一地表示为若干质数的乘积。形如
(\(P_i\) 为质数，\(c_i\ge 0\))
约数
若整数 \(n\) 除以整数 \(d\) 的余数为 \(0\)，即 \(d\) 能整除 \(n\)。
则称 \(d\) 是 \(n\) 的约数，\(n\) 是 \(d\) 的倍数。记为 \(d|n\)。
若正整数 \(n\) 被唯一分解为 \(n=P_1c_1P_2c_2⋯P_mc_m\)，其中 \(c_i\) 都是正整数，\(P_i\) 都是质数。
且满足$ P_1<P_i<...<P_m$，则 \(n\) 的正约数集合为 ：
\(n\) 的正约数个数为 ：
n 的所有正约数的和为：
求正约数集合
求 \(n\) 的正约数集合：试除法
一个整数 \(n\) 的约数个数上界为 \(2\sqrt{n}\)。
求 \(1\) 到 \(n\) 每个数的正约数集合：倍数法
\(1\) 到 \(n\) 每个数的约数个数的总和大约为 \(nlogn\)。
反素数
对于任何正整数 \(x\)，其约数个数记作 \(g(x)\)。例如：\(g(1)=1\)，\(g(6)=4\)。
如果某个正整数满足：
对于任意的 \(0<i<x\)，都有 \(g(x)>g(i)\)，那么称 \(x\) 为反素数。
求不超过 \(N\) 的最大的反素数。
\(1\le N\le 2\times 10^9\)
\(1\) 到 \(N\) 中最大的反素数，就是 \(1\) 到 \(N\) 中约数个数最多的数中最小的一个。
\(1\) 到 \(N\) 中任何数的不同质因子都不会超过 \(10\) 个，且所有质因子的指数总和不超过 \(30\)。
\(\forall x \in [1,n]\)，\(x\) 为反素数的必要条件是：\(x\) 分解质因数后可写作
并且
综上，DFS 即可。
余数之和
给出正整数 \(n\) 和 \(k\)，请计算：
最大公约数和最小公倍数
令 \(a\) 和 \(b\) 是不全为 \(0\) 的两个整数。
能使 \(d|a\) 和 \(d|b\) 的最大整数称为 \(a\) 和 \(b\) 的最大公约数，用 \(gcd(a,b)\) 表示。
或者记为 \((a,b)\)。
能使 \(a|d\) 和 \(b|d\) 的最小整数称为 \(a\) 和 \(b\) 的最小公倍数，用 \(lcm(a,b)\) 表示。
或者记为 \([a,b]\)。
求解最大公约数
更相减损术：
有
有
欧几里得算法（辗转相除法）：
最小公倍数
若 \(a|m\) 且 \(b|m\)，则 \(lcm\ a,b|m\)
若 \(m,a, b\) 是正整数，则 \(lcm (ma,mb)=m\times lcm(a,b)\)
互质与欧拉函数
\(\forall a,b\in \mathbb{n}\)，若 \(gcd(a,b)=1\)，则称 \(a,b\) 互质。
\(1\) 到 \(N\) 中与 \(N\) 互质的数的个数被称为欧拉函数，记为 \(\varphi(N)\)。
若 \(N=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\)，则：
-
\(\forall n>1\)，\(1\) 到 \(n\) 中与 \(n\) 互质的数的和为 \(n\times \varphi (n)/2\)。
-
若 \(a\)，\(b\) 互质，则 \(\varphi ab=\varphi\ a\ \varphi (b)\)
积性函数：\(a\)，\(b\) 互质时，有 \(f(ab)=f(a)\times f(b)\)，那么称函数 \(f\) 为积性函数。
-
若 \(f\) 是积性函数，且在算术基本定理中 \(n=\varsigma i=1m\ p_i\ c_i\) 则 \(f n=\varsigma i=1m\ f(p_i\ c_i)\)。
-
设 \(p\) 为质数，若 \(p|n\) 且 \(p\ 2\ |n\) 则 \(\varphi n=\varphi(\frac{n}{p})\times p\)。
-
设 \(p\) 为质数，若 \(p|n\) 且 \(p\ 2 \nmid n\) 则 \(\varphi n=\varphi(\frac{n}{p})\times (p-1)\)
-
\(\sum \limits_{d|n}\varphi(d)=n\)
线性筛求欧拉函数
for(int i=2;i<=n;i++){
if(!p[i]){
pri[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
p[i*pri[j]]=true;
if(!i%pri[j]) {
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
else
phi[i*pri[j]]=phi[i]*(pri[j]-1);
}
}
2.同余
模运算
\((a+b)\mod m=((a\mod m)+(b\mod m))\mod m\)
\((a-b)\mod m=((a\mod m)-(b\mod m))\mod m\)
\((a\times b)\mod m=((a\mod m)\times(b\mod m))\mod m\)
基本概念
除法定理：对于任何整数 \(a\) 和任何正整数 \(b\)，存在唯一整数 \(q\) 和 \(r\)，满足 \(0 \le r < m\) 且 \(a = qm+r\)，其中 \(q=\lfloor\frac{a}{m}\rfloor\) 为商，\(r=a\mod m\) 为余数。
同余：如果 \(a \mod m=b \mod m\)，即 \(a\), \(b\) 除以 \(m\) 所得的余数相等，记作：\(a\equiv b(\mod m)\)。
裴蜀定理
对任何整数 \(a\),\(b\)，关于未知数 \(x\) 和 \(y\) 的线性不定方程（称为裴蜀等式）：\(ax+b\)
方程有整数解（当且仅当 \(c\) 是 \(gcd(a,b)\) 的倍数）。
裴蜀等式有解时必然有无穷多个解。
\(ax+by=c\) 有解的充要条件为 \(gcd(a,b)|c\)。
一定存在 \(x\),\(y\) 满足 \(ax+by=gcd(a,b)\)。
\(a,b\) 互质等价于 \(ax+by=1\) 有解。
扩展欧几里德算法
void exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
逆元求解
\(ax \equiv 1(\mod m)\)
利用扩展欧几里得算法求逆元，相当于解方程：\(ax+my=1\)。
利用欧拉定理求逆元，有 \(a\times a^{\varphi(m)−1}\equiv 1(\mod m)\) ，可用快速幂求解。
当 \(m\) 为质数时，答案为 \(qpow(a,m-2)\mod m\)。
线性求逆元：递推
求 \(1\) 到 \(n\) 所有数模 \(p\)（\(p\) 为质数且 \(n<p\)）意义下的逆元。
当求 \(i\) 的逆元时，考虑 \(p=iq+r\)，有：\(iq+r \equiv 0(\mod p)\)。
由于 \(p\) 是质数，所以 \(r\) 不为 \(0\)，\(r\) 的逆元存在。
等式两边同乘 \(i^{-1}r^{-1}\)，得到 \(qr^{-1} + i^{-1}\equiv 0(\mod p)\)。
因此：\(i^{−1}\equiv −qr^{−1} \equiv −p_i(p \mod i)^{-1} (\mod p)\)。
for(int i=2;i<=n;i++)
inv[i]=inv[p%i]*(p-p/i)%p;
线性同余方程
形如 \(ax\equiv c(\mod m)\) 的方程为线性同余方程。
线性指 \(x\) 的系数为一次。
该方程可转化为 \(ax+my=c\) 后利用扩展欧几里得算法求解。
根据裴蜀定理，方程有解当且仅当 \(gcd(a,m)|c\)。
线性同余方程组
考虑形如 \(x\equiv a_i (\mod m_i)\) 的若干方程联立得到的方程组，如：
今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？
中国剩余定理
对于同余方程组 \(x\equiv a_i(\mod m_i) (i=1...n)\)，若 \(m_i\) 两两互质，则 \(x\) 在 \(\mod M\) 下有唯一解。
其中 \(M=m_1m_2...mn\)。
令 \(M_i=Mm_i\) 有 \((M_i,m_i)=1\)，\(M_i\) 关于模 \(m_i\) 的逆元存在，设逆元为 \(t_i\)。
故解为
通解
for(int i=1;i<=n;i++)
M*=a[i];
for(int i=1;i<=n;i++){
m[i]=M/a[i];
exgcd(m[i],a[i],t[i],y);
ans+=b[i]*m[i]%M*t[i]%M;
ans%=M;
}
3.组合计数
加法原理和乘法原理
加法原理：
完成一件事的方法有 \(n\) 类，第 \(i\) 类包括 \(a_i\) 种不同的方法，且这些方法互不重合。
则完成这件事共有 \(a_1+a_2+...+a_n\) 种不同的方法。
乘法原理：
完成一件事需要 \(n\) 个步骤，第 \(i\) 个步骤有 \(a_i\) 种不同的完成方法，且这些步骤互不干扰。
则完成这件事共有 \(a_1\times a_2\times ...\times a_n\) 种不同的方法。
排列数和组合数
从 \(n\) 个不同元素中依次取出 \(m\) 个元素排成一列，产生的不同排列的数量为：
从 \(n\) 个不同元素中取出 \(m\) 个组成一个集合（不考虑顺序），产生的不同集合数量为：
\(C_n^m = \frac{n!}{(n - m)!}=\frac{n \times(n - 1) \times...\times(n - m + 1)}{m \times(m - 1)\times......\times}2\times1\)
组合数的性质
\(C_n^m=C_n^{n−m}\)
\(C_n^m=C_{n−1}^m+C_{n-1}^{m−1}\)
\(C_n^0+C_n^1 +C_n^2+...+C_n^n= 2^n\)
二项式定理
4.附录
\(|\) 整除
\(a|b\) 意思为 \(b\) 能整除 \(a\)
"\(\nmid\)"
\(a \nmid b\)意思为 \(b\) 不能整除 \(a\)
\(\equiv\) 同余
$\in\ \ni\ \notin $他的头朝哪边另一边就是这边的因数，斜杠则代表不是。
\(\forall\)任意