P1593. 因子和

发表于 分类于 阅读次数： Waline： 本文字数： 523 阅读时长 ≈ 2 分钟

考点

  • 算术基本定理
  • 快速幂
  • 乘法逆元

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LEN = 1e8 + 50, MOD = 9901;
// 记录有多少个质因子，对应质因子的幂次
ll tot, pri[LEN], cnt[LEN];

//快速幂
ll ksm(ll a, ll b, ll mod) {
  ll ans = 1;
  while (b) {
    if (b & 1) ans = (ans * a) % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ans;
}

//费马小定理求逆元
ll inv(ll a, ll mod) { return ksm(a, mod - 2, mod); }

//算术基本定理拆分质因子
void decompose(ll a, ll b, ll mod) {
  for (ll i = 2; i <= a / i; ++i) {
    if (a % i) continue;
    pri[++tot] = i;
    while (a % i == 0) a /= i, ++cnt[i];
  }
  if (a > 1) pri[++tot] = a, ++cnt[a];
  for (int i = 1; i <= tot; ++i) {
    cnt[pri[i]] *= b;
  }
}

int main() {
  ll a, b;
  cin >> a >> b;
  decompose(a, b, MOD);
  ll ans = 1;
  for (int i = 1; i <= tot; ++i) {
    ll p = pri[i];
    //此时费马小定理不可用
    if ((p - 1) % MOD == 0) {
      ans = (ans * (cnt[p] + 1)) % MOD;
    } else {
      ans =
          (ans * (inv(p - 1, MOD) * (ksm(p, cnt[p] + 1, MOD) - 1 + MOD) % MOD) %
           MOD) %
          MOD;  // 算术基本定理求解约数和
    }
  }
  cout << ans;
  return 0;
}

思路

题目本身不难，算术基本定理+费马小定理+快速幂模板即可，但是坑点很多：

  1. 必须全换成long long，否则会溢出

  2. 快速幂的结果可能为0，那么ksm(p, cnt[p] + 1, MOD) - 1将会是负数

    应当先加MOD后再取模，即(ksm(p, cnt[p] + 1, MOD) - 1 + MOD) % MOD

  3. 如果(p - 1) % MOD == 0，即\(p-1\equiv 0\left( mod\,\,MOD \right)\)

    此时不满足费马小定理的前提条件，也就没有乘法逆元

    根据算术基本定理，有\(a^b=\left( {p_1}^{k_1}{p_2}^{k_2}\cdots {p_m}^{k_m} \right) ^b={p_1}^{bk_1}{p_2}^{bk_2}\cdots {p_m}^{bk_m}\)

    那么约数和等于 $$ \frac{{p_1}^{bk_1+1}-1}{p_1-1}\frac{{p_2}^{bk_2+1}-1}{p_2-1}\cdots \frac{{p_m}^{bk_m+1}-1}{p_m-1} $$

​ 根据等比数列展开一下 \[ \left( 1+p_1+\cdots +{p_1}^{bk_1} \right) \left( 1+p_2+\cdots +{p_2}^{bk_2} \right) \cdots \left( 1+p_m+\cdots +{p_m}^{bk_m} \right) \] ​ 为节约篇幅，只观察\(\left( 1+p_m+\cdots +{p_m}^{bk_m} \right) \left( mod\,\,MOD \right) \\\)， ​ 若有：\(p_m\equiv 1\left( mod\,\,MOD \right)\) ​ 根据同余式的性质，显然上式能化简成：\(\left( bk_m+1 \right) \left( mod\,\,MOD \right)\)