约数之和

博客已搬迁至空白之间

假设现在有两个自然数A和B，S是AB的所有约数之和。
请你求出S mod 9901的值是多少。

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

输出格式
输出一个整数，代表S mod 9901的值。

数据范围
0≤A,B≤5×10^7
输入样例：
2 3
输出样例：
15
注意: A和B不会同时为0。

思路：
1、将S分解质因数
S = a ^ b = p1 ^ ( k1 * b) * p2 ^ (k2 * b)……pn ^(kn * b)
其中p1、p2、……pn都是a的质因数
2、由约数和公式我们可知
res = (1 + p1 ^ 1 + p1 ^ 2 +……p1 ^ (k1 * b))……( 1 + pn ^ 1 + pn ^ 2 +…… pn ^ (kn * b) )
3、我们令sum（p , k） = (1 + p ^ 1 + p ^ 2 + p ^ 3 + …… + p ^ k)
4、当k是偶数的时候，我们可以推出来
sum(p , k) = (1 + p ^ (k / 2)) * sum(p , k / 2) - p ^ (k / 2);
5、当k是奇数的时候，我们可以推出来
sum(p , k) = (1 + p ^ ( (k + 1) / 2 ) ) * sum(p , (k - 1) / 2)
ps：这题要特判a是0的时候
代码：

#include <iostream>
#include <unordered_map>

using namespace std;

const int mod = 9901;
typedef long long LL;


LL qmi(LL a , LL b)
{
    LL res = 1;
    while(b)
    {
        if(b & 1)
            res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

LL sum(LL p ,LL k)
{
    if(k == 0)
        return 1;
    if(k % 2 == 0)
        return ((1 + qmi(p , k / 2)) * sum(p , k / 2) - qmi(p , k / 2)) % mod;
    else
        return (1 + qmi(p , (k + 1) / 2)) * sum(p , (k - 1) / 2) % mod;
}

int main(void)
{
    LL a , b , res = 1;
    unordered_map<int , int >mp;
    
    cin >> a >> b;
    if(a == 0)
    {
        cout << 0 << endl;
        return 0;
    }
    
    for(int i = 2 ; i <= a / i ; i++)
        while(a % i == 0)
        {
            mp[i] += 1;
            a /= i;
        }
    if(a > 1) mp[a] += 1;
    
    for(auto t : mp)
        res = res * sum(t.first , t.second * b) % mod;
    cout << res << endl;
    return 0;
}