分治/质因数分解 POJ1845 求pow(a, b)的所有约数之和

//POJ1845 求pow(a, b)的所有约数之和
//方法：1，分解质因数，将a分解成p1^ k1* p2^ k2^...*pn^ kn
//2, 那么pow(a, b)为p1 ^ (k1* b)* p2 ^ (k2* b)^...*pn ^ (kn* b)
//3，对于单独的pi ^ (ki * b)，他所有的约数为(1, pi, pi ^ 2, pi ^ 3.....pi ^ (ki * b));
//4, 那么整个式子来说，pow(a, b)的所有约数和等于(1 + p1, p1 ^ 2, p1 ^ 3 + .....p1 ^ (ki * b))* (1 + p2, p2 ^ 2 + p2 ^ 3 + .....p2 ^ (ki * b))
//* (1 + pn + p1 ^ 2 + pn ^ 3 + .....p1 ^ (kn * b))，其中每个部分为等比数列
//5，先想到的是等比数列的求和公式，由于取模运算对于加减乘适用，但对于除法不适用，所以转换思路，才用分治法
//6，使用分治法求sum(p, c) = 1 + p ^ 2 + p ^ 3 + ... + p ^ c;
//如果c为奇数
//则1 + p + p ^ 2 + .... + p ^ c = 1 + p + .... + p ^ (c - 1) / 2+
//p^(c+1)/2+....+p^c
//= 1 + p + p ^ 2 + .... + p ^ c = 1 + p + .... + p ^ (c - 1) / 2+
//p^(c+1)/2*(1 + p + p ^ 2 + .... + p ^ c = 1 + p + .... + p ^ (c - 1) / 2)
//=(1+p^(c+1)/2)*sum(p,(c-1)/2)
//同理，当c为偶数时
//=(1+p^(c)/2)*sum(p^c/2-1)+p^c

#include<bits/stdc++.h>
using namespace std;
long long a, b;
int MOD = 9901;
int m;
int prime[100001], c[100001];
long long res;
//质因数分解
void divide(long long n)
{
m = 0;
for (int i = 2; i <= sqrt(n); i++)
{
if ((n % i) == 0)
{
prime[++m] = i, c[m] = 0;
}
while (n % i == 0)n /= i, c[m]++;
}
//n本身为质数
if (n > 1)prime[++m] = n,c[m]=1;
}

//快速幂
long long pow(long long a, long long b)
{
long long ans = 1;
while(b)
{

if(b&1)
ans = (a*ans)% MOD;
a = (a * a) % MOD;
b >> 1;
}
return ans;
}

long long sum(long long p,long long c)
{
if (c == 0 )return 1;
int ans = 0;
if (c & 1)return (1 + pow(p, (c + 1) / 2)) * sum(p, (c - 1) / 2)%MOD;
else return (1 + pow(p, c / 2))* sum(p, c / 2 - 1)%MOD + pow(p, c)%MOD;
}

int main()
{
cin >> a >> b;

divide(a);
res = 1;
for(int i=1;i<=m;i++)
{
res = res*sum(prime[i], c[i] * b)%MOD;
}

cout << res << endl;

}