经典算法 约数之和

原题目链接

问题描述

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

请你计算：S mod 9901 的值。

---

输入格式

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

---

输出格式

输出一个整数，表示 S mod 9901 的值。

---

数据范围

• 0 ≤ A, B ≤ 5 × 10^7
• A 和 B 不会同时为 0

---

输入样例

2 3

---

输出样例

15

c++代码

#include<bits/stdc++.h>using namespace std;typedef long long ll;ll A, B;//求a^b对p取模
ll mypow(ll a, ll b, ll p) {if (b == 0) return 1 % p;if (b == 1) return a % p;__int128_t k = mypow(a, b / 2, p);if (b % 2 == 0) return (k * k) % p;else return (k * k * a) % p;
}//求p^0 + p^1 + p^2 + p^3 + ... + p^k
ll sum_of_a_geometric_series(ll p, ll k) {if (k == 0) return 1;if (k == 1) return 1 + p;if (k % 2 == 0) {ll a = mypow(p, k, 9901);ll b = a + sum_of_a_geometric_series(p, k - 1);return b % 9901;}else {ll a = mypow(p, k / 2 + 1, 9901) + 1;ll b = a * sum_of_a_geometric_series(p, k / 2);return b % 9901;}
}ll prime_factorization() {if (A == 0) return 0;if (A == 1 || B == 0) return 1;ll ans = 1;for (int i = 2; i <= A; i++) {ll cont = 0;while(A % i == 0) A /= i, cont++;if (cont == 0) continue;cont *= B;ans *= sum_of_a_geometric_series(i, cont);ans %= 9901;}return ans;
}int main() {cin >> A >> B;cout << prime_factorization();return 0;
}//by wqs