AcWing 97. 约数之和
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#include <unordered_map>
#define ll long long
#define ull unsigned long long
#define re return
#define pb push_back
#define Endl "\n"
#define endl "\n"
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
const int M = 1e5 + 10;
const int mod = 9901;
const int INF = 0x3f3f3f3f;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int T;
int a, b;
ll ksm(ll a, ll b){
ll res = 1 % mod;
while(b){
if(b & 1)
res = res * a % mod;
b >>= 1;
a = a * a % mod;
}
return res;
}
ll sum(ll p, ll c){
if(c == 0)
return 1;
if(c & 1)
return (1 + ksm(p, (c + 1) / 2)) % mod * sum(p, (c - 1) / 2) % mod % mod;
else
return (((1 + ksm(p, c / 2)) * sum(p, c / 2 - 1)) % mod + ksm(p, c) % mod) % mod;
}
void solve(){
cin >> a >> b;
ll ans = 1;
for (int i = 2; i <= a / i; i++){
if(a % i == 0){
int s = 0;
while(a % i == 0){
s++;
a /= i;
}
ans = ans * sum(i, b * s) % mod;
}
}
if(a > 1)
ans = ans * sum(a, b) % mod;
if(a == 0)
ans = 0;
cout << ans << endl;
}
int main(){
T = 1;
// cin >> T;
while(T--){
solve();
}
}
同时这个分治求法也能很快的求出来等比数列的和,这个是通用的