POJ-1845 Sumdiv 题解

题目大意

求$A^B$的所有约数之和mod9901。

解题思路

（菜鸡的我，还在补基本算法。。

对A进行分解质因数，表示为$p_1^{c_1}\times p_2^{c_2}\times …..\times p_n^{c_n}$。

那么$A^B$就是乘以一个B。

由我不知道的公式得

约数和为$(1+p_1+p_1^2+…+p_1^{c_1\times B})\times (1+p_2+p_2^2+…+p_2^{c_2\times B})\times …\times (1+p_n+p_n^2+…+p_n^{c_n\times B})$。

那么题目就转变为对这些等比数列求乘积了。

对每一项分治可以得到一个递推公式。

当c为奇数的时候$sum(p,c) = (1+p+…+p^{\frac {c-1} {2}})+p^{\frac {c+1}{2}}(1+p+…+p^{\frac {c-1} {2}})=(1+p^{\frac {c+1}{2}})\times sum(p,\frac {c-1}{2})$。

同理，当c为偶数的时候$sum(p,c) = (1+p^\frac {c}{2})*sum(p,\frac {c}{2}-1)\ +p^c$。

完整代码

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 1e5 + 5,M = 9901;
ll prime[N], cnt[N];

ll qpow(ll a, ll b, ll m) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans = (ans * a % m) % m;
		a = (a*a)%m;
		b >>= 1;
	}
	return ans;
}

ll slove(ll a,ll b,ll m) {
	ll ans = 0;
	if (!b)	return 1;
	if (b & 1)	ans = (1 + qpow(a, (b + 1) / 2, m))%m * slove(a, (b - 1) / 2,m)%m;
	else  ans = (1 + qpow(a, b / 2, m)) * slove(a, b / 2 - 1,m)%m + qpow(a, b, m)%m;
	return ans;
}

int main() {
	int a, b;
	cin >> a >> b;
	if (!a && b)	cout << 0 << endl;
	else if (a && !b)	cout << 1 << endl;
	else {
		int i = 2, c = 0;
		while (i * i <= a) {//分解质因数
			if (a % i == 0) {
				prime[c++] = i;
				while (a % i == 0) {
					a /= i,cnt[c - 1]++;
				}
			}
			if (i == 2)	i = 3;
			else i += 2;
		}
		if (a != 1) {//如果a本身是质数
			prime[c++] = a, cnt[c - 1]++;
		}
		ll ans = 1;
		for (int i = 0; i < c; i++)
			ans = (ans*slove(prime[i],cnt[i]*b,M)%M) % M;//记住要乘以b
		cout << ans << endl;
	}
}