经典算法 约数之和

原题目链接
问题描述

假设现在有两个自然数 A 和 B，设 S 为 A^B 的所有约数之和。
请你盘算：S mod 9901 的值。

---

输入格式

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

---

输出格式

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

---

数据范围

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

---

输入样例

1. 2 3

复制代码

---

输出样例

1. 15

复制代码

c++代码

1. #include<bits/stdc++.h>
3. using namespace std;
5. typedef long long ll;
7. ll A, B;
9. //求a^b对p取模
10. ll mypow(ll a, ll b, ll p) {
11.     if (b == 0) return 1 % p;
12.     if (b == 1) return a % p;
13.     __int128_t k = mypow(a, b / 2, p);
14.     if (b % 2 == 0) return (k * k) % p;
15.     else return (k * k * a) % p;
16. }
18. //求p^0 + p^1 + p^2 + p^3 + ... + p^k
19. ll sum_of_a_geometric_series(ll p, ll k) {
20.     if (k == 0) return 1;
21.     if (k == 1) return 1 + p;
22.     if (k % 2 == 0) {
23.         ll a = mypow(p, k, 9901);
24.         ll b = a + sum_of_a_geometric_series(p, k - 1);
25.         return b % 9901;
26.     }
27.     else {
28.         ll a = mypow(p, k / 2 + 1, 9901) + 1;
29.         ll b = a * sum_of_a_geometric_series(p, k / 2);
30.         return b % 9901;
31.     }
32. }
34. ll prime_factorization() {
35.     if (A == 0) return 0;
36.     if (A == 1 || B == 0) return 1;
37.     ll ans = 1;
38.     for (int i = 2; i <= A; i++) {
39.         ll cont = 0;
40.         while(A % i == 0) A /= i, cont++;
41.         if (cont == 0) continue;
42.         cont *= B;
43.         ans *= sum_of_a_geometric_series(i, cont);
44.         ans %= 9901;
45.     }
46.     return ans;
47. }
49. int main() {
50.     cin >> A >> B;
51.     cout << prime_factorization();
52.     return 0;
53. }//by wqs

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。