约数之和

Description

Consider two natural numbers A and B. Let S be the sum of all natural divisors of. Determine S modulo 9901 (the rest of the division of S by 9901).

考虑两个自然数 A 和 B。设 S 为所有自然除数的之和。求 S 除以 9901 的余数。

Input

The only line contains the two natural numbers A and B, ()separated by blanks.

Output

The only line of the output will contain S modulo 9901.

Sample Input

1

2 3

Sample Output

1

15

.
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).

Limit

Analysis

分析样例，对于，有约数 1,2,4,8。我们通过只能得到 1,2，通过能得到 1,2,4。根据规律可以猜想：

假设通过函数可取得数的约数集合，对于，其约数集合为：

证明：

根据算术基本原理，设有两个不同的质因子，即。
那么。
它的所有约数的普遍形式是，其中且。

公式生成的两个集合分别能覆盖的范围：

1. 左半边：
   这里的约数指数不能超过。所以覆盖的范围是且。
2. 右半边：
   因为乘了一个（也就是乘了），原来集合里的和同时加了 1。
   所以覆盖的范围是且。

会遗漏极端情况，比如

故猜想不正确，不过根据因数构造新因数的思想应该是没问题的。

换一个思路，由「算术基本原理」：
每个大于 1 的自然数，要么本身是质数，要么可以写成若干个质数的乘积，且如果不计较质数的排列顺序，这种写法是唯一的。任意正整数 n 可以写成

其中 p 是质数，a 是指数。

在本题，有：

而的全部约数可由质因数构造，其中任意一个约数都可以唯一地表示为：

那么本题的要求可表示为：

接下来需要化简该公式以便于编程。

假设有一个数。
根据约数的构造规律，它的任何一个约数都可以写成，其中且。

它的所有约数之和，就是把所有和组合出的约数全部穷举并相加。一共项：

现在，我们逆用乘法分配律。
首先，按照的次幂把这 6 项分成 3 组，并分别提取公因式：

• 提取第一组的：
• 提取第二组的：
• 提取第三组的：

代入原式：

此时发现，成为了共同的因子。我们再次把这个公因式提取出来，就得到了两个括号相乘：

注：

这是一个等比数列的累乘，更方便编程求解。

推广到个质因子，的所有约数之和逆用乘法分配律，可以转化为各个质因子的等比数列之和的连乘积：

简写为：

由于括号内是首项为、公比为的等比数列，利用等比数列求和公式，可以进一步化简：

本题要求计算，即最终的目标为：

Solve

对于质因数的分解，有这样的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13

void div(int val) {
    for(int i = 2; i <= val / i; ++i) {
        if(val % i == 0) {
            int p = 0;
            while(val % i == 0) {
                ++p;
                val /= i;
            }
            cout << i << ' ' << p << '\n';
        }
    }
    if(val > 1) cout << val << " 1\n";
}

对于可以通过的快速幂求解：

1
2
3
4
5
6
7
8
9

int power(int i, int j) {
    int ans = 1ll % MOD, t = i;
    while(j) {
        if(j & 1) ans = ans * 1ll * t % MOD;
        t = t * 1ll * t % MOD;
        j >>= 1;
    }
    return ans;
}

对于等比数列求和部分，虽然前面我们推导出了公式，但在模运算意义下，除法必须转化为乘以分母的乘法逆元。然而，当恰好是 9901 的倍数时，逆元不存在，这就需要我们在代码里做额外的特判。

为了避开求逆元和特判的麻烦，我们可以使用分治法来计算等比数列的和。设。

利用二分思想，我们可以将整个多项式从中间劈开，按的奇偶性分情况讨论：

1. 当为奇数时：
   整个数列共有项（偶数项），可以完美平分为前后两半。

我们把后半部分的公因式提取出来：

合并同类项，得到化简后的递推式：

2. 当为偶数时：
   数列共有项（奇数项），无法平分。我们可以先把最后一项单独拿出来，此时前面剩下的项最高次幂为（奇数），就可以复用上面的平分逻辑了。

对前半部分进行平分提取（由于最高次幂是，前半部分的一半项到了，提取的公因式为）：

这种分治求和的方法，每次递归都会让减半，递归深度为。结合内部调用的快速幂，整体时间复杂度为。

代码实现如下：

1
2
3
4
5

int sum(int p, int c) {
    if(c == 0) return 1;
    if(c & 1) return (1 + power(p, (c + 1) / 2)) * sum(p, (c - 1) / 2) % MOD;
    return (1 + power(p, c / 2)) * sum(p, (c / 2) - 1) % MOD + power(p, c) % MOD;
}

最终实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <iostream>

const int MOD = 9901;

int a, b;
int power(int i, int j) {
    int ans = 1ll % MOD, t = i;
    while(j) {
        if(j & 1) ans = ans * 1ll * t % MOD;
        t = t * 1ll * t % MOD;
        j >>= 1;
    }
    return ans;
}

int sum(int p, int c) {
    if(c == 0) return 1;
    if(c & 1) return (1 + power(p, (c + 1) / 2)) * sum(p, (c - 1) / 2) % MOD;
    return (1 + power(p, c / 2)) * sum(p, (c / 2) - 1) % MOD + power(p, c) % MOD;
}

int divsum(int num) {
    int ans = 1;
    for(int i = 2; i <= num / i; ++i) {
        if(num % i == 0) {
            int p = 0;
            while(num % i == 0) {
                num /= i;
                ++p;
            }
            ans = ans * sum(i, p * b) % MOD;
        }
    }
    if(num > 1) ans = ans * sum(num, b) % MOD;
    return num ? ans : 0;
}

int main () {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    std::cin >> a >> b;
    std::cout << divsum(a);
    
    return 0;
}

在 divsum 函数中，使用 for(int i = 2; i <= num / i; ++i) 来寻找质因子。

• 在最坏情况下（例如本身是质数），循环会执行到。
• 内层的 while(num % i == 0) 不断做除法，所有这些除法的总执行次数严格受限于。
• 这一部分的时间复杂度为。

对于每一个找出的质因子，都会调用 sum(i, p * b) 计算等比数列和。

• 设有个不同的质因子，最多调用次 sum 函数。由于，在给定的数据范围内，可视为极小的常数。
• 在单次 sum(p, c) 中，递归深度为，每次递归内部又调用了时间复杂度为的 power 函数。
• 这一部分的单次时间复杂度为，因为最大的为，故可近似记作。

整体时间复杂度为 。
空间复杂度则由递归调用的栈深度决定，为 。

结合题目给定的极限数据规模：

Ref

• Nowcoder: Sumdiv
• Acwing: 约数之和