约数之和

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

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

输入格式

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

输出格式

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

数据范围

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

输入样例：

2 3

输出样例：

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)$，分开情况讨论就可以得到最终的答案。

看代码

#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;
}