第一部获得式子
然后发现是等比数列求和
然后发现如果套公式需要求逆元
众所周知 求逆元有无非常见的有两种
一 取得数与mod 互质, 直接调用欧拉定理 $a^{mod-2} $ 即是逆元
二 直接用扩展欧几里得求解
显然这个题不能直接用欧拉函数(因为 mod 很小而 A 很大 所以可以有 与 mod 不互质得 A)
但是会发现, mod 是 9901 那么如果直接用等比公式得话 项数不会很多 最多不过 $ 3 * B $
并且!符合情况 即 (p - 1) 是 9901 得倍数且 p 是质数得数字很少!!!!!
所以直接调用欧拉定理, 如果不互质,暴力求当前等比数列和。。互质,直接套公式求逆元, 虽然取巧,证明我也不会, 但是跑的飞快!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 9901;
ll add(ll a, ll b) {
a %= mod, b %= mod;
return ((a + b) % mod + mod) % mod;
}
ll mul(ll a, ll b) {
a %= mod, b %= mod;
return (a * b % mod + mod) % mod;
}
ll quick(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = mul(ans, a);
a = mul(a, a);
b >>= 1;
}
return ans;
}
int main() {
ll a, b; cin >> a >> b;
if (!a) {
cout << 0 << endl;
return 0;
}
ll ans = 1;
for (int i = 2; i <= a; ++i) {
ll k = 0;
while (a % i == 0) {
k++;
a /= i;
}
if (!k) continue;
k *= b;
// 1 + q + q^2 + q^3
// Sn=a1 (1-q^n)/ (1-q)= (a1-anq)/ (1-q)
if ((i - 1) % mod) {
ll s = 1 * (quick(i, k + 1) - 1) * (quick(i - 1, mod - 2));
ans = mul(ans, s);
} else {
ll s = 0;
for (int j = 0; j <= k; ++j) {
s = add(s, mul(ans, quick(i, j)));
}
ans = s;
}
}
cout << mul(ans, 1) << endl;
return 0;
}