约数之和

约数之和

假设现在有两个自然数 $A$ 和 $B$,$S$ 是 $A^B$ 的所有约数之和。

请你求出 $Smod9901$ 的值是多少。

输入格式

在一行中输入用空格隔开的两个整数 $A$ 和 $B$。

输出格式

输出一个整数,代表 $Smod9901$ 的值。

数据范围

$0≤A,B≤5\times 10^7$

输入样例:

1
2 3

输出样例:

1
15

解析

要求 $A^B$ 的所有约数和,先求 $A$ 的所有约数和,即对 $A$ 进行质因数分解,得到式子,$A = \prod ^n_{i = 1} p_i^{c_i}$,那么可以得到 $A^B = \prod ^n_{i = 1} p_i^{c_i\times B}$,即可以得到 $A^B$ 的约数之和,为:$\prod^n_{i = 1}(1 + p^1_i + p^2_i + ..+p^{c_i\times B}_i)$如果单纯的计算每个算式,这个复杂度就会与质因数的个数和 $B$ 的乘积有关,会超时。

再观察括号内的式子满足等比数列规律,但根据等比数列的求和公式,分母分子同时会含有公比 $q$ ,分子分母不能同时 $MOD$ 后作除法,所以无论是 $S = \frac{a_1-a_nq}{1-q}$ 还是 $S = \frac {a_1(1-q^n)}{1-q}$,都可能会被数据卡掉(前者的 $a_nq$ 和 后者的 $a_1q^n$,A、B一大就会卡掉)。

一条路走不通 再返回去看式子(这里假设式子中无B),

设 $n = 5$

就会有 $p^0 + p^1 + p^2 + p^3 + p^4 + p^5$ 总共 6 个数,我们将其拆分成相同个数的两份

$(p^0 + p^1 + p^2) + (p^3 + p^4 + p^5)$

然后再化简 $(p^0 + p^1 + p^2) + p^3(p^0 + p^1 + p^2)$

继续可得 $(p^0 + p^1 + p^2)\times(1 + p^3)$ ,这里是 $n$ 为奇数的情况

同理,当 $n$ 为偶数时(n = 4),可得最终式子$(p^0 + p^1) \times(1 + p^2) + p^4$

综上两种情况,再配合快速幂这样我们就把 $O(n)$ 时间复杂度的式子变成了 $O(log^2n)$,分开情况讨论就可以得到最终的答案。

看代码

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
34
35
36
37
38
39
#include <cstdio>

const int MOD = 9901;

int ans = 1, A, B;

int qmi(int a, int b) {
a = a % MOD; //注意这里要先模
int val = 1 % MOD;
while(b) {
if(b & 1) val = val * a % MOD;
b = b >> 1;
a = a * a % MOD;
} return val;
}

int sum(int n, int k) {
if(k == 0) return 1;
if(k & 1) return sum(n, k >> 1) * (1 + qmi(n, (k >> 1) + 1)) % MOD;
else return sum(n, (k >> 1) - 1) * (1 + qmi(n, k >> 1)) % MOD + qmi(n, k) % MOD;
}

int main() {
scanf("%d %d", &A, &B);

for (int i = 2; i <= A; i++) {
int tot = 0;
while(!(A % i)) {
tot++;
A /= i;
}

if(tot) ans = ans * sum(i, tot * B) % MOD;
}

if(A == 0) ans = 0;
printf("%d", ans);
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!