约数之和

题目

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

输入格式

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

输出格式

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

输入样例

2 3

输出样例

15

思路

模板题，约数和定理，递归

关于递归
约数和定理

代码

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

const int M = 9901;

int qmi(int a, int b)
{
    a %= M;
    int res = 1;  //乘积初始化为1
    while (b)
    {
        if (b&1) res = res * a % M;
        a = a * a % M;
        b >>= 1; //右移>>
    }
    return res;
}

int sum(int p, int k)
{
    if (k == 0) return 1;
    if (k & 1) return sum(p, k / 2)  % M * (1 + qmi(p % M, k / 2 + 1) % M) % M; //中间变量取模，防止溢出
    else return (sum(p % M, k - 1) % M * p % M + 1) % M; 
}

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

    int res = 1; //累积初始化为1
    for (int i = 2; i <= a; i++)
    {
        int s = 0;
        while (a % i == 0)
        {
            s ++ ;
            a /= i;
        }
        if (s) res = res % M * sum(i, s * b) % M; //指数为s*b
    }
    if (!a) res = 0;
    cout << res << endl;
}