约数

定义：$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];
            }
        }
    }
}