約數之和

• 2020 年 2 月 18 日
• 筆記

約數之和

題目描述

假設現在有兩個自然數A和B，S是$A^B$的所有約數之和。

請你求出S mod 9901的值是多少。

輸入格式

在一行中輸入用空格隔開的兩個整數A和B。

輸出格式

輸出一個整數，代表S mod 9901的值。

數據範圍

$0≤A,B≤5×10^7$

輸入樣例：

2 3

輸出樣例：

15

注意: A和B不會同時為0。

題解

考慮將$A$進行質因數分解.

$A = prod_{i = 1} ^ {n} p_i ^ {a_i} = p_1 ^ {a_1} p_2 ^ {a_2} p_3 ^ {a_3} … p_n ^ {a_n}$

那麼

$A^B = prod_{i = 1} ^ {n} p_i ^ {a_i B} = p_1 ^ {a_1 B} p_2 ^ {a_2 B} p_3 ^ {a_3 B} … p_n ^ {a_n * B}$

$S$定義為$A^B$的約數和，那麼

$S = prod_{i = 1}^n sum_{j=0}^{a_i*B} p_i^j $

$S= (p_1^0+p_1^1+…+p_1^{a_1B})(p_2^0+p_2^1+…+p_2^{a_2B})…(p_n^0+p_n^1+…+p_n^{a_nB})$

式子看似複雜，簡單的講就是相當於在式子中的每一個因子項。也就是每一個括弧裡面取一個。然後取得$n$相乘起來就得到了一個$A^B$的約數。

現在我們的問題就是求:$sum_{j=0}^{a_i*B}p_i^j$

容易看出。這是一個等比數列前n項和。省賽就做過一個這個玩意兒。當時想複雜了。想成用等比數列前$n$項和公式，但是當時它那個題目的模數是輸入，也就是模數可能是合數。這題中模數確定是9901。是一個素數。可以考慮使用等比數列求和公式。當然，可以使用分治，

#include <bits/stdc++.h>  using namespace std;    #define dbg(x) cerr << #x"=" << x << endl;  typedef long long LL;  #define p first  #define a second  const int MOD = 9901;    LL powN(LL a, LL n){      LL res = 1LL;      while(n){          if(n&1) res = res * a % MOD;          a = a * a % MOD;          n >>= 1;      }      return res;  }    // 計算p^0+p^1+...+p^a  LL cal(LL p, LL a){      if(a == 0) {          return 1;      }      int h = a >> 1;      if(!(a&1)){          --h;      }      LL ans = cal(p, h);      LL ah = powN(p, h+1);      ans = (ans + ah * ans % MOD) % MOD;      if(!(a&1)){          ans = (ans + powN(p, a)) % MOD;      }      return ans;  }    int main(){      //freopen("in.txt", "r", stdin);      LL A,B;      cin >> A >> B;      if(A == 0 || A == 1){          cout << A << endl;          return 0;      }      map<LL, LL> mp;      for(LL i = 2; i*i <= A; ++i){          while(A%i == 0){              mp[i]++;              A /= i;          }      }      if(A > 1) mp[A]++;      LL ans = 1LL;      for(auto x : mp){          x.a *= B;          ans = ans * cal(x.p, x.a) % MOD;      }      cout << ans << endl;      return 0;  }