【解题报告】BZOJ 1951 [SDOI2010]古代猪文

发表于

传送门

$\text{Solution}$

题目意思是求解

如果没有那个指数，这个题目还是很方便的，直接 $O(\sqrt{n})$ 扫一遍就可以了，但是有一个指数，所以 $P$ 不能直接取模，而要根据 费马小定理 :

其中 $p$ 是质数。

这就是说 $P$ 要对 $999911658$ 取模，而这就是 拓展卢卡斯定理 的事了。实际上我们对 $999911658$ 质因数分解，可以得到 $999911658=2\times3\times4679\times35617$ 。这样我们可以预处理出阶乘，可以快速求解答案。

最后一个坑点，当 $G = 999911659$ 时答案显然是 $0$ 而不是 $1$ ，需要特判

$\text{Code}$

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
#define Mod 999911659
int A[5], M[5], fact[5][40000];
int ModularPow(int a, int p, int k) {
	int ans = 1;
	while (p) {
		if (p & 1)	ans = (ans * a) % k;
		a = (a * a) % k;
		p >>= 1;
	}
	return ans;
}
int ExtendedGCD(int a, int b, int& x, int& y) {
	if (a == 0 && b == 0) return -1;
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int value = ExtendedGCD(b, a % b, y, x);
    y -= a / b * x;
    return value;
}
inline int ModReverse(int a, int p) {
	int x, y, value = ExtendedGCD(a, p, x, y);
	return value == 1 ? (x + p) % p : -1;	
}
inline int C(int n, int m, int p) {
	if (m > n) return 0;
	int id = p == 2 ? 1 : (p == 3 ? 2 : (p == 4679 ? 3 : 4));
	return fact[id][n] * ModReverse(fact[id][m], p) % p * ModReverse(fact[id][n - m], p) % p;
}
inline int Lucas(int n, int m, int p) {
	if (m == 0) return 1;
	return C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}
inline int CRT() {
    int ans = 0, lcm = Mod - 1;
    for (int i = 1; i <= 4; i++) {
        int tmp = lcm / M[i];
        (ans += A[i] * tmp * ModReverse(tmp, M[i])) %= lcm;
    }
    return (ans + lcm) % lcm;
}
inline int ExtendedLucas(int n, int m) {
	for (int i = 1; i <= 4; i++) 
		A[i] = Lucas(n, m, M[i]);
	return CRT();
}
inline int solve(int n) {
	M[1] = 2, M[2] = 3, M[3] = 4679, M[4] = 35617;
	for (int i = 1; i <= 4; i++) {
		fact[i][0] = 1;
		for (int j = 1; j <= M[i]; j++)
			fact[i][j] = fact[i][j - 1] * j % M[i];
	}
	int ans = 0;
	for (int i = 1; i * i <= n; i++)
		if (n % i == 0) {
			(ans += ExtendedLucas(n, i)) %= (Mod - 1);
			if (i * i != n) (ans += ExtendedLucas(n, n / i)) %= (Mod - 1);
		}
	return ans;
}
signed main() {
	int n, g;
	std::cin >> n >> g;
	if (g == Mod) std::cout << "0" << std::endl; 
	else std::cout << ModularPow(g, solve(n), Mod) << std::endl;
	return 0;
}