IT评测·应用市场-qidao123.com技术社区

标题: 经典算法 约数之和 [打印本页]
作者: tsx81428    时间: 2025-4-9 02:23
标题: 经典算法 约数之和
原题目链接
问题描述

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

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

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


输入样例

  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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4