筛约数和

以下文章尚未完善，仅供参考

约数和

求n的约数和

根据惟一分解定理 $$n=p_1^{\alpha_1} p_2{ }^{\alpha_2} \cdots p_s^{\alpha_s}, (p_1<p_2<\cdots<p_s)$$

则$f(n) = {\textstyle \prod_{i=1}^{s}} {\textstyle \sum_{j=0}^{a_{i}}}p_{i}^{j} $

证明：

$p_{i}^{a_{i}}$的约数有 $p^{0},p^{1},\cdots,p^{a_{i}}$ 共 ($a_{i} + 1$)个

则约数和为${\textstyle \sum_{j=0}^{a_{i}}}p_{i}^{j}$,根据分步组合，乘法原理 $f(n) = {\textstyle \prod_{i=1}^{s}} {\textstyle \sum_{j=0}^{a_{i}}}p_{i}^{j} $

求 `n`的约数和

先求出所有的因数及对应的幂次方

然后连乘积即可

下面的问题是如何求${\textstyle \sum_{j=0}^{a_{i}}}p_{i}^{j}$

设 $S(n)=x^{0}+x^{1}+x^{2}+\cdots+x^{n}$

$S(n) = 1 + x\times(x^{0}+x^{1}+\cdots+x^{n-1}) $

$= 1 + x\times S(n-1)$ 如此反复直到 $S(1) = 1$ 所以可以一开始初始化 $t = 1$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


int main(){ 
    int n;
    scanf("%d",&n);
    unordered_map<int,int>  map;
    //获取约数 和 约数的幂
    while(n--){
        int x;
        std::cin>>x;
        for(int i = 2;i<=x/i;++i){
            while(x % i == 0){
                x/=i;
                ++map[i];
            }
        }
        if(x > 1) ++map[x];  
    }    
    ll ans = 1;
    //开始求连乘积
    for(auto p : map){

        ll t = 1;
        ll a = p.first ;
        ll b = p.second;
        //∑  1 + x*s(n-1) 
        while(b--){
            t = (t*a+1);
        }
        //∏连乘积
        ans = (ans*t);
    }
    printf("%lld\n",ans)
    return 0;
}

求 1~n 约数之和

前置知识

欧拉筛法

筛约数个数

这上面的约数定理这里不再证明

其中 g[k] 保存当前第k最小质因子的和

${\textstyle \sum_{j=0}^{a_{k}}}p_{i}^{k}$

f[k] 保存k位置的约数和

利用g[]来递推f[]

若$i$为质数的情况

整数唯一分解后 : $p^{0} + p^{i}$

那么显然

1

g[i] = f[i] = 1 + i;

若为合数的情况

若 i%pj == 0

$m = pj * i$

则 $m$ 一定是被$pj$最小质因子筛掉，这里不再证明请看之前的前置知识

$g[i] = p^{0}+p^{1}+\cdots +p^{a_{i}}$

因为贡献了一个最小质因子$pj$ ,

$g[m] = p^{0}+p^{1}+\cdots +p^{a_{i+1}}$

那怎么用$g[i]$ 递推出 $g[m]$ ? 可以再开一个数组来保存最小质因子$pj$的次数 ?但没必要

x注意到：pj与其他质数互质.又由组合原理

$g[m] = 1 + p^{1}+\cdots +p^{a_{i+1}}$ 提出一个$pj$

$g[m] = 1 + pj\times(p^{0}+\cdots +p^{a_{i}})$

∴$g[m] = 1 + pj\times g[i]$

1

g[m] = 1+p[j]*g[i];

$f[i] = g[i]\times \cdots \times 1$

由于$m = pj * i$ ${\textstyle \sum_{j=0}^{a_{k}}}p_{i}^{k}$的部分多了 pj的贡献所以要变为$g[m]$

当然了中间的部分是之前递推的显然不变

既为$f[m] = g[m]\times \cdots\times 1$ , 而中间部分为 $ \frac{f[i]}{g[i]}$

∴ $f[m] = g[m] \times \frac{f[i]}{g[i]}$

1

f[m] = f[i] / g[i] * g[m];

若 i % pj != 0

说明 $i$ 并不包含最小质因子 $pj$ ，又因为枚举的$pj$是从小到大的, 也就是说 m的整数分解只能分解出 $pj$ 这一质因子既$g[m] = pj^{0} + pj = 1 + pj$

$m = pj * i$ ，因为$pj$ 为最小质因数根据分步原理和乘法原理

$f[m] = g[m] \times f[i]$

留个小疑问为什么这里不像上面 i % pj == 0的情况做除法而是可以直接使用 f[i] 呢?

答案 : 因为pj 并不是 $i$的最小质因子

$f[i] = g[i] \times \cdots\times 1$ 不能直接拿贡献修改$g[i]$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


const int N = 1000010;
int p[N], vis[N], cnt;
//g[i]表示i的最小质因子的1+p^1+...+p^k
int g[N], f[N];//f[i]表示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];
      }
    }
  }
}

via:

https://www.acwing.com/solution/content/145781/

约数和

求 n的约数和

求 1~n 约数之和

求 `n`的约数和