Micnation_AFO @ 2022-03-04 22:54:13
rt
input:
488 1314
Dev-c++:
-3695
VSC:
6184
Code:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 9901
int a, b;
int ans = 1;
int power(int a, int b) {
int ans = 1 % mod;
a %= mod, b %= mod;
for (; b; b >>= 1) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
int sumdiv(int p, int c) {
if (c == 0) return 1;
if (c % 2 == 1) return ((power(p, (c + 1) / 2) + 1) % mod) * sumdiv(p, (c - 1) / 2) % mod;
else return (sumdiv(p, c - 1) + power(p, c)) % mod;
}
signed main() {
cin >> a >> b;
int n = a;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i != 0) continue;
int cnt = 0;
while (a % i == 0) a /= i, cnt++;
ans = ans * sumdiv(i, cnt * b) % mod;
}
if (a != 1) ans = ans * sumdiv(a, 1 * b) % mod;
cout << ans << endl;
return 0;
}
by Micnation_AFO @ 2022-03-04 22:55:06
顺便求大佬帮忙看看为啥 40 pts,做法是分解质因数然后用分治法求等比数列的和
by Micnation_AFO @ 2022-03-04 23:00:58
提供一组 hack 数据
114514
191981
(这么大也没用是吧
by Natsume_Rin @ 2022-03-04 23:10:42
@Leap_hash_jperm 在 power
中,指数 b %= mod;
删了就过了。
by Natsume_Rin @ 2022-03-04 23:12:02
另外,这边好像在 Windows 系统下,Dev 运行你的代码是输出
by Micnation_AFO @ 2022-03-04 23:12:56
@Emy_Ycc 谢谢!指数确实不能取模
by Micnation_AFO @ 2022-03-04 23:13:39
windows DEV小熊猫版