题目描述

假设现在有两个自然数A和B，S是AB的所有约数之和。

请你求出S mod 9901的值是多少。

样例

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

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

数据范围
0≤A,B≤5×107

输入样例：
2 3
输出样例：
15

递归

1.等比数列的计算
2.快速幂
3.将一个数分解成个数相乘
4.如何把结果的取模转化到算法中的各个步骤(待解决)

C++ 代码

#include <cstdio>
#include <iostream>
using namespace std;
const int mod = 9901;
int qui_pow(int a,int b)
{
    int res=1;
    a %= mod;
    while(b>0)
    {
        if(b&1)
            res=a*res % mod;;
        a=a*a% mod;
        b>>=1;
    }
    return res;
}
int sum_(int q,int k)
{
    if(k==0)
        return 1;
    if(k%2==0)
        return (q%mod*sum_(q,k-1)% mod+1)% mod;
    if(k%2==1)
        return (1+qui_pow(q,k/2+1))% mod*sum_(q,k/2)% mod;
}
int main()
{
    int a,b;
    int cnt=0;
    int sum=1;
    cin>>a>>b;
    for(int i=2;i<=a;i++)
    {
        while(a%i==0)
        {
            cnt++;
            a/=i;
        }
        if(cnt!=0)
            sum=sum_(i,cnt*b)*sum% mod;
        cnt=0;
    }
    if(a==0)
        sum=0;
    cout<<sum;

}