题目链接

算法竞赛进阶指南-10.约数之和

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

请你求出 $S \bmod 9901$ 的值是多少。

输入格式

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

输出格式

输出一个整数，代表 $S \bmod 9901$ 的值。

数据范围

$0 \le A,B \le 5 \times 10^7$

输入样例：

2 3

输出样例：

15

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

Method : 分治

#include <unordered_map>
#include <iostream>

using namespace std;

typedef long long LL;

const int MOD = 9901;

int a, b;
unordered_map<int, int> primes;

LL fast_pow(LL a, LL b) {
    LL res = 1LL % MOD;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
    }
    
    return res;
}

int sum(int p, int k) {
    if (k == 1) return 1;
    if (k % 2 == 0) {
        return (fast_pow(p, k/ 2) + 1) * sum(p, k / 2) % MOD;
    }
    else {
        return (fast_pow(p, k - 1) + sum(p, k - 1)) % MOD;
    }
}

int main() {
    cin >> a >> b;
    
    for (int i = 2; i <= a / i; i ++) {
        while (a % i == 0) {
            a /= i;
            primes[i] ++;
        }
    }

    if (a > 1) primes[a] ++;
    
    LL res = 1;
    for (auto& prime : primes) {
        int p = prime.first, k = prime.second * b;
        
        res = res * sum(p, k + 1) % MOD;
    }
    
    if (a == 0) res = 0;
    
    cout << res << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度${O(\log n)}$， 其中$\log n$为对n进行二进制拆分的时间复杂度。

• 空间复杂度${O(1)}$。