97. 约数之和

Powered by:NEFU AB-IN

Link

97. 约数之和

• 题意

  假设现在有两个自然数 A和 B，S是 A^B的所有约数之和。
  请你求出 S mod 9901的值是多少。

• 思路

  $A^B$的约数之和为：$su{m}_{A^B}=(1+p_1+p_1^2+...+p_1^{B\times a_1})\times (1+p_2+p_2^2+...+p_2^{B\times a_2})\times ...$
  为什么最高项是$B\times a$呢，最高项代表$p$这个质因子的个数，一开始$A$有$x$个$p$，那么$A^3=A\times A\times A$就有$3x$个$p$

  • 做法一：等比数列求和 + 快速幂

    所以，对于每个质因子，根据等比数列求和公式 $(1+p+p^2+...+p^{B\times a})=\frac{p^{B\times a+1}-1}{p-1}$
    那么，对$A$进行质因子分解

    • $p^{B\times a+1}$用快速幂求
    • $\frac{1}{p-1}$用费马小定理求逆元，但必须保证$p-1$与$MOD$互质
      • 若$p-1$与$MOD$互质，正常求即可
      • 若$p-1$与$MOD$不互质，我们无法求逆元，就换种思路求表达式。因为 $p\%MOD=1$，$(1+p+p^2+...+p^{B\times a})\%MOD=1+B\times a\times 1=1+B\times a$，所以直接返回$1+B\times a$即可

    复杂度 $O(\sqrt{n}log(n))$

  • 做法二：分治 + 快速幂
    定义 $sum(p,k)=(1+p+p^2+...+p^k)$，共$k+1$项

    • 当$k$为奇数时，项数为偶数，以下默认$\frac{k}{2}=\lfloor \frac{k}{2}\rfloor$
      原式$=(p^0+p^1+...+p^{\frac{k}{2}})+(p^{\frac{k}{2}+1}+...+p^k)=(p^0+p^1+...+p^{\frac{k}{2}})+p^{\frac{k}{2}+1}\times (p^0+p^1+...+p^{\frac{k}{2}})=(1+p^{\frac{k}{2}+1})\times sum(p,\frac{k}{2})$
    • 当$k$为偶数时，转化为奇数情况，$sum(p,k)=sum(p,k-1)+p^k$

    复杂度 $O(\sqrt{n}log(n)log(n))$

  • 超时做法三：递推
    求$(p^0+p^1+...+p^k)$，可用递推式，ans = ans * p + 1，但此做法会超时

• 代码

  做法一

  /** @Author: NEFU AB-IN* @Date: 2023-02-18 11:22:46* @FilePath: \Acwing\97\97.cpp* @LastEditTime: 2023-02-18 23:11:41*/
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #undef int#define SZ(X) ((int)(X).size())
  #define ALL(X) (X).begin(), (X).end()
  #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 9901;int quickmod(int a, int b)
  {a %= MOD;int res = 1;while (b){if (b & 1)res = res * a % MOD;a = a * a % MOD;b = b >> 1;}return res % MOD;
  }signed main()
  {IOS;int a, b;cin >> a >> b;if (!a){cout << 0;return 0;}// 质因子分解unordered_map<int, int> mp;for (int i = 2; i <= a / i; ++i){while (a % i == 0){mp[i]++;a /= i;}}if (a > 1)mp[a]++;int ans = 1;auto f = [&](int p, int n) {if ((p - 1) % MOD == 0)return n + 1;int pp = quickmod(p, n + 1);int ny = quickmod(p - 1, MOD - 2);return (pp - 1 + MOD) * ny % MOD;};for (auto [x, cnt] : mp){ans = ans * f(x, cnt * b) % MOD;}cout << ans;return 0;
  }

  ---

  做法二

  /** @Author: NEFU AB-IN* @Date: 2023-02-18 12:21:32* @FilePath: \Acwing\97\97.1.cpp* @LastEditTime: 2023-02-19 11:36:53*/
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #undef int#define SZ(X) ((int)(X).size())
  #define ALL(X) (X).begin(), (X).end()
  #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 9901;int quickmod(int a, int b)
  {a %= MOD;int res = 1;while (b){if (b & 1)res = res * a % MOD;a = a * a % MOD;b = b >> 1;}return res % MOD;
  }int sum(int p, int k)
  {if (k == 0)return 1;if (k % 2 == 0)return sum(p, k - 1) % MOD + quickmod(p, k) % MOD;return sum(p, k / 2) % MOD * (1 + quickmod(p, k / 2 + 1)) % MOD;
  }int main()
  {IOS;int a, b;cin >> a >> b;if (!a){cout << 0;return 0;}// 质因子分解unordered_map<int, int> mp;for (int i = 2; i <= a / i; ++i){while (a % i == 0){mp[i]++;a /= i;}}if (a > 1)mp[a]++;int ans = 1;for (auto [x, cnt] : mp){ans = ans * sum(x, cnt * b) % MOD;}cout << ans;return 0;
  }