AcWing 97. 约数之和
原题链接
中等
作者:
dajianer
,
2021-05-20 18:52:13
,
所有人可见
,
阅读 291
P17 分治
#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
const int mod = 9901;
const int maxn = 50;
void factor(int n, int a[maxn], int b[maxn], int &tot) {
int temp, i, now;
temp = (int) ((double)sqrt(n) + 1);
now = n;
tot = 0;
for (i = 2; i <= temp; i++) {
if (now % i == 0) {
//cout << tot << "\n";
a[++tot] = i;
b[tot] = 0;
while (now % i == 0) {
b[tot]++;
now /= i;
}
}
}
if (now != 1) {
a[++tot] = now;
b[tot] = 1;
}
}
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = ans * a % mod;
b >>= 1;
a = a * a % mod;
}
return ans;
}
int sum(int a, int b) {
if (b == 0) return 1;
if (b % 2) return (1 + qpow(a, (b+1)/2)) % mod * sum(a, (b - 1) / 2) % mod;
if (b % 2 == 0) return ((1 + qpow(a, b/2)) % mod * sum(a, b/2-1) % mod + qpow(a, b)) % mod;
}
signed main() {
int a, b;
cin >> a >> b;
int aa[50], bb[50];
int tot;
factor(a, aa, bb, tot);
int ans = 1;
for (int i = 1; i <= tot; i++) {
ans = (ans * sum(aa[i], bb[i]*b)) % mod;
}
if (a == 0) cout << "0\n";
else
cout << ans << "\n";
}