约数之和

题目描述：

输入A，B，求 A^B的所有约数之和在mod 9901下的值

思路：

根据唯一分解定理可以把A分解成：

A = a_1^{p_1}*a_2^{p_2}*…*a_k^{p_k}

则 A^B = a_1^{B*p_1}*a_2^{B*p_2}*…*a_k^{B*p_k}

所以约数之和

所以我们只需要解决因数分解以及求类似 (a_1^0+a_1^1+..+a_1^{B*p1})

假设sum(a,x) = (a^0+a^1+…+a^{x-1})

• x是偶数时，利用指数相乘时底数不变，指数想加的方法可以得出 $sum(a,x) = sum(a, x/2) + sum(a, x/2)\*a^{x/2}$
• x是奇数时，只需要把最后一项拿出来，则可以利用偶数方法计算，sum(a, x) = sum(a, x-1) * a^{x-1}

这其实就是递归的过程

当然，这个题的模数只有9901，任何一个数字的幂次最多经过9900次就会产生重复，所以我们可以记录循环节来直接计算sum(a,x),计算一次最多需要循环9901次，A最多也就十几个质因子，所以复杂度差不多是1e5级别的

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define m_p(a, b) make_pair(a, b)
typedef long long ll;
typedef pair<int, int> pii;
#define MAX 300005
#define mod 9901
int n, m, d, x, k;
ll sum[MAX];

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

ll fuck(ll x, ll k){
	if(k == 1)return 1;
	if(k % 2 == 0){
		return (fuck(x, k/2) * (1ll + p_qow(x, k/2)))%mod; 
	}
	else return (fuck(x, k-1) + p_qow(x, k-1))%mod;
}


void work(){
	cin >> n >> m;
	ll ans = 1ll;
	for(ll i = 2; i * i <= n; ++i){
		if(n % i == 0){
			ll num = 0;
			while(n % i == 0){
				++num;
				n /= i;
			}
			num *= m;
			(ans *= fuck(i, num+1))%=mod;
		}
	}
	if(n > 1)(ans *= fuck(n, 1+m))%=mod;
	if(!n)cout << 0 << endl;
	else cout << ans << endl;
}


int main(){
	//int t;cin >> t;while(t--)
	work();
	return 0;
}