对于约数和公式的一些见解

对于约数和公式的一些见解

wizard（偷开O2

·

2024-01-04 16:49:57

·

个人记录

前几天看到了一道关于约数和的一道好题，题目大意就是求出 A^B 的所有约数之和（模数我忘了）。

对此次的学习进行一个记录。

①质因数分解

约数和公式其实非常好推导，本质上就是对底数 A 的一个质因数分解。

所以我们从对 A 的质因数分解讲起。

我们初中学过一个算术基本定理，里面讲过说一个正整数（大于1）都能被分解成有限个质数的乘积，而且这种分配方式唯一。

理出来就是 A= p_1^{c_1} * p_2^{c_2} * ... * p_n^{c_n} 。

但是怎么用程序实现这种分解呢，我在这只说一种简单的试除法,还有一种效率更高的算法Pollard's rho我会新建一篇博客记录。

这种方法与欧拉筛的思想几乎相同，扫一遍 2 ~ \sqrt{A} 内的所有整数，如果遇到一个数可以整除 A 那么就以他为底数循环直到搜出他的最大指数。

我举个例子：24。在做循环的时候，我们遇到的第一个可以整除24的数字就是2。利用试除法可以得到他的指数为3。最后剩余的数字在对其进行试除。得到最终结果为: 24=2^3* 3^1。

特别的，如果说最后剩余的 A 大于1，那么 A 一定为质数，代码实现下来复杂度应该是 O(\sqrt A)。

int devide(int n){

int p[maxn],c[maxn];

int m=0;

for(int i=2;i*i<=n;i++){

if(n%i==0){

p[++m]=i;c[m]=0;

while(n%i==0){

c[m]++;

n/=i;

}

}

}

if(n>1){

p[++m]=n;

c[m]=1;

}

}

②推导

刚刚我们已经对底数 A 做了质因数分解，那么 A^B 就可以表示为 A^B= p_1^{B* c_1} * p_2^{B* c_2} * ... * p_n^{B* c_n} 。

在对刚才的举例进行一个探讨24=2^3* 3^1，我们对 2，3的指数进行一个更换，发现若指数小于现在的指数的话，结果依然是24的约数，那么就可以得出约束表示的集合就是 {p_1^{k_1}*...*p_n^{k_n}} ，且 0 \le k_i \le B*c_i(1 \le i \le n)。

利用分配律，可以得到A 的约数和公式为\prod_{i=1}^n \sum\limits_{j = 0}^{B* c_i} p_i^j

③实现

最普通的一种可以提高效率的方法就是分治法。

提出一个疑问，如何用分治法求出 1+ p^1+....+p^c。

对此，我们需要对 c 为奇数还是偶数两种情况来分类讨论。

若c为奇数：

work(p,c)=(1+p^1+...+p^{(c-1)/2})+(p^{(c+1)/2}+...+p^c)

=(1+p^1+...+p^{(c-1)/2})+p^{{c+1}/2} \times (1+p^1+...+p^{(c-1)/2})

=(1+p^{(c+1)/2}) \times work(p,(c-1)/2)

若c为偶数:

work(p,c)=(1+p^1+...+p^{((c/2)-1})+(p^{c/2}+...+p^{c-1})+p^c

=(1+p^1+...+p^{((c/2)-1})+p^{c/2} \times (1+p^1+...+p^{((c/2)-1})+p^c

=(1+p^{c/2}) \times (1+p^1+...+p^{((c/2)-1})+p^c

=(1+p^{c/2}) \times work(p,(c/2)+1)+p^c

时间复杂度大概在 O(\operatorname{log} c)。