题目描述

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

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

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

数据范围
0 ≤ A, B ≤ 5 × 10 ^ 7

输入样例：

2 3

输出样例：

15

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

对递推式进行取模运算，令p = 9901
b = 0时，1无需取模
b为奇数时，递归式等号右边是两个多项式相乘的形式，取模的分配律对乘法有效。因此，
对p取模的结果是：((1 + a ^ (b / 2) + 1) * sum(a, b / 2)) % p
b为偶数时， sum(a, b) = 1 + a * sum(a, b - 1)
给定的数据范围是0 ≤ A, B ≤ 5×10 ^ 7，由于偶数情况下是在奇数的结果之上计算的。按最大范围考量。
a与sum(a, b - 1)相乘会溢出。如果单单只是sum(a, b -1)对p取模乘积仍然有溢出的可能。
为了保险起见，对a和sum(a, b - 1)分别对p取模再求乘积然后再对p取模一次。因此，才有
(1 + a % p * sum(a, b - 1) % p) % p; 这样取模目的就是为了确保相乘的时候绝对不溢出。

大脑链路对信息的传导迟钝，一开始这样取模真还没反应过来。hh

按道理，也可以用偶数来递推奇数的。以后再试试。

算法

C++ 代码

#include <iostream>
using namespace std;
const int p = 9901;

int qmi(int a, int b) {
    int ans = 1 % p;
    a %= p;  // 别忘了，每个质因数都要取模，怕溢出，到处取模。
    for(; b; b >>= 1) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
    }
    return ans;
}

int sum(int a, int b) {
    if(b == 0) return 1;
    if(b % 2 == 0) return (1 % p + a % p * sum(a, b - 1) % p) % p;
    return (1 + qmi(a, b / 2 + 1)) * sum(a, b / 2) % p;
}

int main() {
    int a, b;
    cin >> a >> b;
    int ans = 1;
    for(int i = 2; i <= a; i++) {
        int s = 0;
        while(a % i == 0) {
            s++;
            a /= i;
        }
        if(s) ans = ans * sum(i, s * b) % p;
    }
    if(!a) ans = 0;
    cout << ans << endl;
    return 0;
}