2025-09-21 18:09:06
发布于：广东
#include <bits/stdc++.h>
using namespace std;
vector<int> primes;
bool is_prime[2000005]; // 最大到2e6
// 线性筛法预处理质数
void sieve(int max_n) {
memset(is_prime, true, sizeof(is_prime));
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= max_n; ++i) {
if (is_prime[i]) {
primes.push_back(i);
}
for (int p : primes) {
if (i * p > max_n) break;
is_prime[i * p] = false;
if (i % p == 0) break;
}
}
}
// 计算n!中质因子p的指数
int count_factor(int n, int p) {
int cnt = 0;
while (n) {
cnt += n / p;
n /= p;
}
return cnt;
}
// 快速幂计算a^b mod mod
long long pow_mod(long long a, long long b, long long mod) {
long long res = 1;
while (b > 0) {
if (b % 2 == 1) {
res = (res * a) % mod;
}
a = (a * a) % mod;
b /= 2;
}
return res;
}
int main() {
int n, p;
cin >> n >> p;
if (n == 0) {
cout << 1 % p << endl;
return 0;
}
int max_fact = 2 * n;
sieve(max_fact);
long long ans = 1;
int m = n + 1; // 卡特兰数公式中的n+1
for (int prime : primes) {
if (prime > max_fact) break;
// 计算(2n)!中prime的指数
int cnt = count_factor(2 * n, prime);
// 减去n!的指数（两个n!）
cnt -= 2 * count_factor(n, prime);
// 减去m中prime的指数（因为要除以m）
int cnt_m = 0;
int temp = m;
while (temp % prime == 0) {
cnt_m++;
temp /= prime;
}
cnt -= cnt_m;
// 计算prime^cnt mod p
if (cnt > 0) {
ans = (ans * pow_mod(prime, cnt, p)) % p;
} else if (cnt < 0) {
// 若指数为负，说明m与p不互质且有公因子未被完全约去，结果为0
cout << 0 << endl;
return 0;
}
}
cout << ans % p << endl;
return 0;
}
这里空空如也
有帮助，赞一个