数论基础F
约数
定义：\(a|b\) 表示 \(a\) 整除于 \(b\) （\(b\) 能被 \(a\) 整除），\(b\) 为 \(a\) 的倍数，\(a\) 为 \(b\) 的约数
规定 \(0\) 是所有非 \(0\) 整数的倍数，且对于非 \(0\) 整数 \(b\) ，\(b\) 的约数只有有限个
对于非 \(0\) 整数 \(b\) ，\(\pm1,\pm b\) 是 \(b\) 的平凡约数（当 \(b=\pm1\) 时，\(b\) 只有两个平凡约数），\(b\) 的其他约数称为真约数（非平凡约数）
满足性质如下：
整数 \(b\ne0\)，给定的 \(d\) 在遍历 \(b\) 的全体约数时，\(\frac{b}{d}\) 也遍历 \(b\) 的全体约数
整数 \(b>0\)，给定的 \(d\) 在遍历 \(b\) 的全体正约数时，\(\frac{b}{d}\) 也遍历 \(b\) 的全体正约数
一般讨论中，我们约定的约数总是指正约数
约数个数定理
对于整数 \(n>1\) ，根据唯一分解定理其可以被分解为若干个质因子的连乘积，表示为
\[n=\prod_{i=1}^{s} p_i^{\alpha _i}=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_s^{\alpha_s}
\]
那么它的约数个数 \(d(n)\) 可以通过下面的表达式得出
\[d(n)=\prod_{i=1}^s (\alpha_i+1)
\]
简单证明如下：
\(p_i^{\alpha_i}\) 的因子有 \(p_1^0,p_i^1,\cdots,p_i^{\alpha_i}\) 共计 \(\alpha_i+1\) 个，递推地计算 \(p_{i+1}^{\alpha_{i+1}}\) 及所有项，根据乘法原理得出 \(d(n)=\prod_{i=1}^s (\alpha_i+1)\)
（若 \(p_i^a,p_j^b\) 都是 \(n\) 的因子，那么 \(p_i^a*p_j^b\) 也是 \(n\) 的因子）
线性筛法求约数个数
筛除合数时，分别考虑两种情况
枚举的 \(i\) 能被 \(p_j\) 整除，则 \(p_j\) 一定是 \(m\) 的最小质因子，于是递推积累最小质因子的次数 \(\alpha_m=\alpha_i+1\)
因为 \(d(i)=(\alpha_i+1)*\cdots,d(m)=(\alpha_m+1)*\cdots\) 所以 \(d(m)\) 由下式计算得出
\[d(m)=d(i)*\frac{1}{\alpha_m}*(\alpha_m+1)
\]
若 \(i\) 不能被 \(p_j\) 整除，则 \(i\) 不包含质因子 \(p_j\)，那么 \(\alpha_m=1,d(m)=d(i)*(\alpha_m+1)=2*d(i)\)
int p[N],cnt;
bool vis[N];
int a[N],d[N];//a用来记录i的质因子的次数alpha_i，d用来记录i的约数个数
void get_d(int n){
d[1]=1;//定义1的约数个数为1
for (int i=2;i<=n;i++){
if (!vis[i]){//如果当前i为质数
p[++cnt]=i;//存进p数组
a[i]=1;//质数的最小质因子是它本身，且次数为1
d[i]=2;//规定质数的约数个数为2
}
for (int j=1;i*p[j]<=n;j++){//筛除以i为最小质因子的合数
int m=i*p[j];
vis[m]=1;//标记合数
if (i%p[j]==0){//确定只被最小质因子筛除
a[m]=a[i]+1;
d[m]=d[i]/a[m]*(a[m]+1);
break;
}else{
a[m]=1;
d[m]=d[i]*2;
}
}
}
}
约数和定理
有 \(n=\prod_{i=1}^sp_i^{\alpha_i}\) ，记 \(n\) 的约数和为 \(f(n)\) ，满足
\[f(n)=\prod_{i=1}^s \sum_{j=0}^{\alpha_i} p_i^j
\]
简单证明如下：
通过约数个数定理可知，\(n\) 的任意一个约数都是在每一个质因子 \(p_1^{\alpha_1},p_2^{\alpha_2},\cdots,p_s^{\alpha_s}\) 中，选出这个质因子 \(p_i^{\alpha_i}\) 的任意一个约数乘法组合而成
那么，不同的选法共有 \(\prod_{i=1}^s (\alpha_i+1)\) 种，即约数个数
那么，它们的和即为
\[(p_1^0+p_1^1+\cdots+p_1^{\alpha_1})\times(p_2^0+p_1^2+\cdots+p_2^{\alpha_2})\times\cdots\times(p_s^0+p_s^1+\cdots+p_s^{\alpha_s})
\]
可以看作分别计算出了每个质因子的约数的每种情况，再相加
线性筛法求约数和
需要记录每个 \(i\) 的最小质因子贡献的累加和，记为 \(g_i\)，其中 \(p_{\gamma}\) 表示 \(i\) 的最小质因子
\[g_i=\sum_{i=0}^{\alpha_i} p_{\gamma}^i
\]
筛除合数时，分别考虑两种情况
枚举的 \(i\) 能被 \(p_j\) 整除，则 \(p_j\) 一定是 \(m\) 的最小质因子，分别计算 \(g_i,g_m\)
\[g_i=\sum_{i=0}^{\alpha_j}p_j^i \ \ ,\ \ g_m=\sum_{i=0}^{\alpha_j+1}p_j^i=g_i*p_j+p_j^0
\]
那么就能从 \(f_i\) 递推到 \(f_m\)
\[f_i=g_i*\prod_{j}^{j\ne i} g_j\ \ ,\ \ f_m=g_m*\prod_j^{j\ne i} g_j=\frac{f_i}{g_i}*g_m
\]
若 \(i\) 不能被 \(p_j\) 整除，则 \(i\) 不包含质因子 \(p_j\)
\[g_m=1+p_j\ \ ,\ \ f_m=g_m*f_i
\]
int p[N],cnt;
bool vis[N];
int g[N],f[N];//g记录i的最小质因子贡献的累加和，f表示i的约数和
void get_f(int n){
g[1]=f[1]=1;
for (int i=2;i<=n;i++){
if (!vis[i]){
p[++cnt]=i;
g[i]=f[i]=i+1;
}
for (int j=1;i*p[j]<=n;j++){
int m=i*p[j];
vis[m]=1;
if (i%p[j]==0){
g[m]=g[i]*p[j]+1;
f[m]=f[i]/g[i]*g[m];
break;
}else{
g[m]=p[j]+1;
f[m]=f[i]*g[m];
}
}
}
}