题目描述

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

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

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

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

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

样例

输入样例：
2 3
输出样例：
15
注意: A和B不会同时为0。

算法1

(等比数列和 + 逆元) $O(sqrt(n)*logn)$

算法描述 ：

根据算术基本定理 N = p1^c1p2^c2.....pn^cn。 即一个数可以表示为若干个质因数^g个数相乘。
因为如AB,则A中的每个质因数个数B。example ：2 = 1 * 2，2^3 = 1^32^3。

对于一个大于1正整数n可以分解质因数：n=p1^a1p2^a2p3^a3…pk^ak,
则由约数个数定理可知n的正约数有(a₁+1)(a₂+1)(a₃+1)…(ak+1)个，
那么n的(a₁+1)(a₂+1)(a₃+1)…(ak+1)个正约数的和为
f(n)=(p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak）

证明：若n可以分解质因数：n=p1^a1p2^a2p3^a3…pk^ak,
可知p1^a1的约数有:p1^0, p1^1, p1^2......p1^a1
…
同理可知，pk^ak的约数有:pk^0, pk^1, pk^2......pk^ak ；
实际上n的约数是在p1^a1、p2^a2、…、pk^ak每一个的约数中分别挑一个相乘得来，
可知共有(a₁+1)(a₂+1)(a₃+1)…(ak+1)种挑法，即约数的个数。
由乘法原理可知它们的和为
f(n)=(p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak）

example ：将360分解质因数可得
360=2^33^25^1
由约数和定理可知，360所有正约数的和为
(2^0+2^1+2^2+2^3)×(3^0+3^1+3^2)×(5^0+5^1)=(1+2+4+8)(1+3+9)(1+5)=15×13×6=1170
可知360的约数有1、2、3、4、5、6、8、9、10、12、15、18、
20、24、30、36、40、45、60、72、90、120、180、360；则它们的和为
1+2+3+4+5+6+8+9+10+12+15+18+20+24+30+36+40+45+60+72+90+120+180+360=1170

因为AB=(1+p11+p12+.....+p1B∗c1)×(1+p22+.....+pnB×c2AB=(1+p11+p12+.....+p1B∗c1)×(1+p22+.....+pnB×c2 )
sum(p,c)=1+p+p2+…+pc

参考文献

百度百科

C++ 代码

#include <iostream>
using namespace std;
typedef long long LL;
const int mod = 9901;

LL quickpow(LL a,LL k){
    LL ans = 1;
    while(k)
    {
        if(k&1)ans = 1ll*ans * a %mod;
        k>>=1;
        a = 1ll*a * a %mod;
    }
    return ans;
}

int main(){
    LL a,b,cnt = 0,res= 1;

    cin>>a>>b;

    if(!a)cout<<0<<endl;
    else
    for(int i = 2 ; i <= a  ; i++)
    if(a%i==0){
        while(a%i==0)
        {
            a/=i;
            cnt++;
        }

        if(i%mod==1)
            res = res*(b*cnt+1)%mod;
        else
        {
            LL x = i % mod; res = 1ll*res*(quickpow(x,b*cnt+1)-1) * quickpow(x-1,mod-2) % mod;
        }
        cnt = 0;
       // cout<<res<<endl;
    }
    if(a) cout<<res%mod<<endl;
    return 0;
}

算法2

(分治+快速冥) $O(lognlogn)$

C++ 代码

#include <iostream>
using namespace std;
typedef long long LL;
const int mod = 9901;

int quickpow(int a,int k){
    LL ans = 1;
    while(k)
    {
        if(k&1)ans = 1ll*ans * a %mod;
        k>>=1;
        a = 1ll*a * a %mod;
    }
    return ans % mod;
}


int sum(int p,int c){
    LL ans = 1;
    if(c==0)return 1;
    else if(c%2)
    {
        ans = ans * (1 + quickpow(p,(c+1)/2))%mod * sum(p,(c-1)/2)% mod;
    }
    else 
        ans = ans * (1 + quickpow(p,c/2))%mod * sum(p,c/2-1) + quickpow(p,c)% mod;
    return ans % mod;
}
int main(){
    LL a,b,cnt = 0,res= 1;

    cin>>a>>b;

    if(!a)cout<<0<<endl;
    else
    for(int i = 2 ; i <= a  ; i++)
    if(a%i==0){
        while(a%i==0)
        {
            a/=i;
            cnt++;
        }
    res = res * sum(i,cnt*b) % mod;
       cnt = 0;
    }
    if(a) cout<<res%mod<<endl;
    return 0;
}