题目描述

假设现在有两个自然数A和B，S是AB

的所有约数之和。

请你求出S mod 9901的值是多少。
输入格式

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

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

0≤A,B≤5×107

样例

输入样例：

2 3

输出样例：

15

注意: A和B不会同时为0。

约数+递归求和

A的质约数有p1,p2,……,pk,各自对应的次项为α1,α1,……,αk
所以A可以表示为：A=(p1)^(α1)……(pk)^(αk);
A的约数个数为：(α1+1)……(αk+1)
A的所有约之和为：(p1^0+……+p1^α1)……(pk^0+……+pk^αk)
那么A^B=(p1)^(α1B)……(pk)^(αkB)
A^B的所有约数之和为：(p1^0+……+p1^α1+……+p1^(α1B))……(pk^0+……+pk^(αkB))
所以只需要把每一项算出来并求积
而计算每一项可以利用递归

C++ 代码

#include<iostream>

using namespace std;

const int mod=9901;

int a,b;

int qmi(int q,int k){
    int res=1;
    q=q%mod;
    while(k){
        if(k&1) res=(res*q)%mod;
        q=(q*q)%mod;
        k=k>>1;
    }
    return res;
}
int sum(int q,int k){
    if(k==1)    return 1;//如果最高次项是0，那么结果为1
    if(k%2) return (sum(q,k-1)+qmi(q,k-1))%mod;
    else    return ((1+qmi(q,k/2))*sum(q,k/2))%mod;
}
int main(){
    cin>>a>>b;
    int res=1;
    for(int i=2;i*i<=a;i++){
        int s=0;
        if(a%i==0){
            while(a%i==0){
                s++;
                a/=i;
            }
            res=(res*sum(i,s*b+1))%mod;//计算i^0+……+i^(s*b)
        }
    }
    if(a>1)   res=(res*sum(a,b+1))%mod;
    if(!a)  res=0;
    cout<<res;
    return 0;
}