颓了一个暑假我终于腆着脸回来更博客了
带模的减法一定要加上模数再取一遍模...
懵逼的 题目
传送至poj
扯淡的 题解
我们惊奇的发现 \(A^B\)的约数和就是
\[
(p_1^0 + p_1^1 + \cdots + p_1^{k_1\cdot B}) \cdot (p_2^0 + p_2^1 +
\cdots +p_2^{k_2\cdot B}) \cdot (p_3^0 + p_3^1 + \cdots + p_3 ^{k_3
\cdot B}) \cdot (\cdots)
\] 的展开, 是不是很神奇?
那么我们只需要对每一个\(p\)求出\((p^0 + p^1 + \cdots + p^{k \cdot
B})\)就可以了
我们又发现, 这个式子其实就是个等比数列求和, 直接套分治板子就行了
然后就因为带模减法减成负数调了一下午... = =
沙茶的 代码
调了好久...肥肠的丑...
对了 千万别忘了是多组数据....
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define INF (50000000 + 5)
#define MAXN (4000000 + 5)
#define Aufun (9901)
#define LL long long
#define pii pair<int, int>
using namespace std;
LL a;
int b;
LL fp(LL pa, int pb)
{
if (pb == 0)
return 1;
LL re = fp(pa, pb >> 1);
re = (re * re) % Aufun;
if (pb & 1)
re = (re * pa) % Aufun;
return re;
}
LL sum(LL p, int c)
{
if (c == 1)
return (p + 1) % Aufun;
if (c == 0)
return 1;
LL re = sum(p, c >> 1);
if (c & 1)
return (re * (1ll + fp(p, (c + 1) >> 1ll))) % Aufun;
else
return (re * (1ll + fp(p, (c >> 1) + 1)) - fp(p, c + 1) + Aufun) % Aufun;
}
int main()
{
freopen("in.in", "r", stdin);
freopen("WA.out", "w", stdout);
while (scanf("%lld%d", &a, &b) == 2)
{
LL ans = 1;
for (int i = 2; i <= sqrt((double)a) + 1; i++)
{
int dq = 0;
while (a % i == 0)
a /= i, ++dq;
ans = (ans * sum((LL)i, dq * b)) % Aufun;
}
if (a > 1)
ans = (ans * sum(a, b)) % Aufun;
printf("%lld\n", ans);
}
return 0;
}
|
By 粉Bandit的彩虹六号萌新 Cansult
Bandit抬头看我的样子真的好帅啊嘤嘤嘤