题解

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

请你求出 Smod9901 的值是多少。

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

输出格式
输出一个整数，代表 Smod9901 的值。

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

分析题意
约数之和：

假设把a分解质因数后为：

pk11∗pk22∗⋯∗pknn
p1k1∗p2k2∗⋯∗pnkn
则a的约数之和就为 :

(1+p1+p21+⋯+pk11)∗(1+p2+p22+⋯+pk22)∗⋯∗(1+pn+p2n+⋯+pknn)
(1+p1+p12+⋯+p1k1)∗(1+p2+p22+⋯+p2k2)∗⋯∗(1+pn+pn2+⋯+pnkn)
假设a被2整除，k = log a,那么总共有blog a 项，a和b都取5*10^7

此题的数据非常大，直接算会超时，此时将等比数列求和分解乘一个个小问题

发现性质
每一个括号都是一个等比数列求和，所以我们写出一个函数专门求解等比数列

sum(p,c)=1+p+p2+⋯+pk
sum(p,c)=1+p+p2+⋯+pk
当k为偶数时，那么式子一共有奇数项，此时我们把第一个1拿出去，把剩下的项提出一个p
​
sum(p,c)=1+p(1+p+p2+⋯+pk−1)
sum(p,c)=1+p(1+p+p2+⋯+pk−1)
​
sum(p,c)=1+p∗sum(p,k−1)
sum(p,c)=1+p∗sum(p,k−1)
此时sum将转化为小问题去解决

当k为奇数时，那么式子一共有偶数项，我们可以将式子从中间分开
​
sum(p,c)=1+p+p2+⋯+pk
sum(p,c)=1+p+p2+⋯+pk
​
sum(p,c)=(1+p+⋯+pk/2)+(pk/2+1+⋯+pk)
sum(p,c)=(1+p+⋯+pk/2)+(pk/2+1+⋯+pk)
​

​ 此时将后面提出个
pk/2+1
pk/2+1
​
sum(p,c)=(1+p+⋯+pk/2)+pk/2+1∗(1+p+⋯+pk/2))
sum(p,c)=(1+p+⋯+pk/2)+pk/2+1∗(1+p+⋯+pk/2))
​

​ 前后一致的括号提出了

​
sum(p,c)=(1+p+⋯+pk/2)∗(1+pk/2+1)
sum(p,c)=(1+p+⋯+pk/2)∗(1+pk/2+1)
​
sum(p,c)=sum(p,k/2)∗(1+pk/2+1)
sum(p,c)=sum(p,k/2)∗(1+pk/2+1)
​

​ 此时sum也转化为小问题解决，这里的
pk/2+1
pk/2+1
可以使用快速幂解决

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int mod = 9901;

ll qmi(int a, int k, int p)
{
    //a %= p;       //这里a的取值为5*10^7,不然开longlong,不然让a先mod p后在操作
    ll res = 1 % p;
    while(k)
    {
        if(k & 1) res = res * a % mod;
        k >>= 1;
        a = (ll)a * a % mod;
    }
    return res;
}

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

int main()
{
    int a, b;
    cin >> a >> b;
    int res = 1;

    for(int i = 2; i <= a / i; i ++ )
    {
        int s = 0;
        while(a % i == 0)
        {
            s ++ ;
            a /= i;
        }
        res = res * sum(i, s * b) % mod;
    }
    if(a > 1) res = res * sum(a, b) % mod;

    if(!a) res = 0;             //a等0时，特判一下
    cout << res << endl;
    return 0;
}