【模板】筛约数个数

前置知识

试除法求约数和试除法求质数是类似的道理

约数必须在整除的前提下才存在,而因数是从乘积的角度来提出的.如果数a与数b相乘的积是数c,a与b都是c的因数。

约数只能对在==正整数==范围内而言,因为0不能整除任何数而因数就不限于整数的范围。

对于一个整数,凡能整除它的数,都是这个整数的约数。约数和因数一样都可以成对出现

输入一个数要求从小到大不重复输出每个约数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


 vector<LL> div(int num){
	vector<LL> v;
	for(LL i = 1;i*i<=num;i++){
		if(num % i == 0){
			v.push_back(i);
            //约数不可重复 4 = 2*2
			if(i*i!=num) v.push_back(num/i);
		}
	}
	sort(v.begin(),v.end());
	return v;
}

复杂度分析

1 ,2 ,3 ···n

2是所有倍数的约数其他同理，则求倍数的个数和求约数的个数一样

1~n当中倍数的个数和约数的个数是一样的

1 + n/2+3/n+···n/n

loglog n 但外层是根号n 总体根号n

欧拉筛约数个数

约数个数定理

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

则$$d(n)=\prod_{i=1}^{n}(a_{i}+1)$$

证明：

根据整数唯一分解性定理，每一个质数次方 $ p_{1}^{a_i}$ 的约数有$ p_{i}^{0}$ , $p_{1}^{1}$,···$p_{1}^{a_i}$ 共(a~i~+1)个选法

根据组合原理和乘法定理，则$ d(n)=\prod_{i=1}^{n}(a_{i}+1) $ 每个质因子幂次数+1的连乘积

那么我们使用a[] 数组来保存最小质因子的次数$a_{0},a_{1}…a_{i} $

而 d[] 自然是保存约数个数

显然 d[] 需要借助a[]来递推

如果为质数

最小质因子初始化为1(本身) , 约数个数初始化为 2 (1 和本身) (1+$a_{i}$)

1
2
3
4


if(!vis[i]){
    p[++cnt] = i;
    a[i] = 1; , d[i] = 2; 
}

接下来在处理合数的过程中

m = i * pj

分为两种情况如果 pj 为m的最小质因子和 pj不是m的最小质因子

若i % pj == 0

$pj$ 一定是$i$ 的最小质因数 , 也一定是$m$的最小质因数

$m = i \times pj$ 若存在更小的质因数在之前早就已经被筛选掉

因为在这里 $pj$ 又贡献了一个最小质因子次数更新 $a[m]$

1

a[m] = a[i] + 1;

那 $d[m]$如何求

由$d(n) = (1+a_{1})\times(1+a_{2})\times\cdots\times(1+a_{n})$

那么$d(i) = (1+a_{1})\times(1+a_{2})\times\cdots\times(1+a_{i})$

= $ (1+a[i])\times(1+a_{2})\times\cdots\times(1+a_{i})$

而$m$ 比 $i$的基础上再多一个最小质因子$pj$ ($i\times pj = m$)

既

$d(m) = (1+1+a_{1})\times(1+a_{2})\times\cdots\times(1+a_{i})$

=$(a[m] + 1) \times(1+a_{2})\times\cdots\times(1+a_{i}) $

借助d[i]

= $(a[m] + 1) \times \frac{d(i)}{(1+a[i])}$

1

d[m] = d[i]/(a[m])*(a[m]+1); //a[m] = a[i] + 1

若i不能被pj整除则 i 不包含质因子pj

1
2
3
4


if(i % p[j] != 0){
    //d[m] = d[i] * d[p[j]] 积性函数性质
    a[m] = 1;d[m] = d[i] * 2;
}

则初始化a[m] = 1 ; 因为i 不包含质因子pj ,此时得到了一个pj(从小到大枚举的) 所以这个1的贡献就是来自pj , m = i * pj, 既pj必然为m的最小质因子贡献1

$d(i) = (1+a_{1})\times(1+a_{2})\times\cdots\times(1+a_{i})\times 1$

又∵$pj$ 为最新贡献且不属于 $i$的因数($i%pj!=0$) 由 乘法原理

$d[m] = (1+a_{1})\times(1+a_{2})\times\cdots\times(1+a_{i})\times (1+1)$

1

d[m] = d[i] * (1+1);

筛选1…n的约数个数

 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


const int N = 100010;
int p[N], cnt;
bool vis[N];
int a[N]; //记录i最小质因子的次数
int d[N]; //d[i] 记录i约数个数

void get_d(int n ){//1..n
    d[1] = 1;
    for(int i = 2;i<=n;i++){
        if(!vis[i]){
            p[++cnt] = i;
            //最小质因数本身，约数就本身 1+1 = 2
            a[i] = 1; , d[i] = 2; 
        }
        for(int j = 1; i*p[j] <= n;j++){
            int m = i*p[j];
            vis[m] = 1;
            if(i%p[j] == 0){
                //如果找到最小质因数 则加上pj贡献1
                a[m] = a[i] + 1;
                d[m] = d[i] / a[m] * (a[m]+1);
                break;
            }else{
                //d[m] = d[i] * d[p[j]] 积性函数性质
                a[m] = 1;d[m] = d[i] * 2;
            }
        }
    }
}

法2

算出n的所有质因子及约数个数

一个合数n中最多只包含一个大于根号n的质因子

最多包括没有这种情况

证明：反证如果有两个大于sqrt(n)的因子，那么相乘会大于n

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


int main(){
    int x;
    std::cin>>x;
    unordered_map<int,int> map;
    for(int i = 2;i<=x/i;++i){
        while(x%i == 0){ //一直分解质因子 唯一分解
            x/=i;
        	++map[i];
        }
        if(x > 1) ++map[x]; //一个合数n中最多只包含一个大于根号n的质因子
    }
    ll ans = 1;//约数个数
    for(auto p : map)
        ans*=(p.second+1);//约数个数公式
}

参考

https://www.involute.top/2021/01/%E7%BA%BF%E6%80%A7%E7%AD%9B%E6%B1%82%E7%BA%A6%E6%95%B0%E4%B8%AA%E6%95%B0/

https://www.cnblogs.com/TheRoadToTheGold/p/8228969.html

https://blog.csdn.net/ControlBear/article/details/77527115