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

Input Format

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

Output Format

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

Input Example:

2 3

Output Example:

15

Note 2 raised to the power of 3 equals 8. The natural divisors of 8 are: 1,2,4,8. Their sum is 15. 15 modulo 9901 is 15 (that should be output).

Problem Analysis

根据算术基本定理: $$ N = p_1^{c_1} \times p_2^{c_2} \times \cdots \times p_n^{c_n} $$ 可知 $$ A = p_1^{c_1} \times p_2^{c_2} \times \cdots \times p_n^{c_n} $$ 那么 $$ A^B = p_1^{c_1 \times B} \times p_2^{c_2 \times B} \times \cdots \times p_n^{c_n \times B} $$ 所有的约数之和为: $$ \text{Sum} = (p_1^0 + p_1^1 + \dots + p_1^{c_1 \cdot B}) \cdot (p_2^0 + p_2^1 + \dots + p_2^{c_2 \cdot B}) \cdot \dots \cdot (p_n^0 + p_n^1 + p_n^{c_n \cdot B}) $$ 对于其中的每一项, 我们可以通过等比数列求和公式进行计算,但是在求和公式的除法中,我们不能进行取模运算。 对公式进行化简,我们可以写出递归式: $$ \text{For } c \cdot B \text{ odd: } \quad \text{sum}(p, c \cdot B) = (1 + p^{(c + 1)/2}) \cdot \text{sum}(p, (c - 1)/2) $$

$$ \text{For } c \cdot B \text{ even: } \quad \text{sum}(p, c \cdot B) = (1 + p^{c/2}) \cdot \text{sum}(p, c/2 - 1) + p^c $$

Code Implementation

#include <iostream>
using namespace std;
using LL = long long;
const LL MOD = 9901;

int a, b;
LL qmi(LL i, LL j) {
    LL ans = 1
    while(j) {
        if(j & 1) ans = ans * 1ll * t
        t = t * 1ll * t
        j >>= 1;
    }
    return ans;
}
LL sum(int p, LL c) {
    if(c == 0) return 1;
    if(c & 1) return (1 + qmi(p, (c + 1) / 2)) * sum(p, (c - 1) / 2)
    else return (1 + qmi(p, c / 2)) * sum(p, (c / 2) - 1)
}
void divide(int num) {
    LL ans = 1;
    for(int i = 2; i <= num / i; ++i) {
        if(num
            LL p = 0;
            while(num
                num /= i;
                ++p;
            }
            ans = ans * sum(i, p * b)
        }
    }
    if(num > 1) ans = ans * sum(num, b)
    cout << (num ? ans : 0);
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> a >> b;
    divide(a);
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status