兔队:

#include <cstdio>

// 宏定义，用于简化循环语句
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define F2(i, a, b) for (int i = (a); i < (b); ++i)

// 定义最大范围
const int MAXN = 1e7 + 1;

// 全局变量声明
int T, Mod, n, m;
int primes[MAXN], pnum = 0;
bool isn_prime[MAXN];
int pi[MAXN], inv[MAXN];
int in[MAXN], fct[MAXN];
int pos[MAXN];

// 初始化函数，进行素数筛选、计算欧拉函数和阶乘
void init() {
	// 素数筛选
	isn_prime[0] = isn_prime[1] = true;
	F(i, 2, MAXN - 1) {
		if (!isn_prime[i]) {
			primes[++pnum] = i;
			// 将 i 的倍数标记为非素数
			for (int j = i * 2; j < MAXN; j += i) {
				isn_prime[j] = true;
			}
		}
	}

	// 计算逆元，用于后续计算
	inv[1] = 1;
	F(i, 2, Mod - 1)
	inv[i] = 1ll * (Mod - Mod / i) * inv[Mod % i] % Mod;

	// 计算 pi 函数值，pi[i] 表示不超过 i 的数中与 i 互质的数的个数
	pi[0] = 1;
	F(i, 1, pnum)
	pi[i] = 1ll * pi[i - 1] * (primes[i] - 1) % Mod;

	// 计算逆元的累积值
	in[0] = 1;
	F(i, 1, pnum)
	in[i] = (primes[i] != Mod) ? 1ll * in[i - 1] * inv[primes[i] % Mod] % Mod : in[i - 1];

	// 计算阶乘的累积值
	fct[0] = 1;
	F(i, 1, MAXN - 1)
	fct[i] = (i != Mod) ? 1ll * fct[i - 1] * i % Mod : fct[i - 1];

	// 计算小于等于 i 的质数的个数
	F(i, 2, MAXN - 1)
	pos[i] = isn_prime[i] ? pos[i - 1] : pos[i - 1] + 1;
}

int main() {
	// 读取测试用例数和模数
	scanf("%d%d", &T, &Mod);
	// 初始化数据
	init();

	// 处理每个测试用例
	while (T--) {
		// 读取 N 和 M
		scanf("%d%d", &n, &m);
		// 判断特殊情况
		if (n >= Mod && m < Mod)
			puts("0");
		else
			// 计算 [1, N!] 中与 M! 互质的数的数量
			printf("%d\n", 1ll * fct[n] * pi[pos[m]] % Mod * in[pos[m]] % Mod);
	}

	return 0;
}

言啄：

#include <cstdio>
#include <algorithm>

// 读取整数
inline int in();
// 输出整数
inline void wr(int);

// 最大范围定义
const int N = (int)1e7 + 5, M = (int)3e6 + 5;
// 存储素数
int p[M], fac[N], p1[M], p2[M];
// 判断素数数组
bool vis[N];

// 素数筛选函数
inline void prime();
// 快速幂取模函数
inline int quick_mod(int, int, int);

int main(int argc, char **argv) {
	// 进行素数筛选
	prime();
	// 读取测试用例数和模数
	register int T = in(), R = in();
	// 预处理阶乘数组
	fac[0] = 1;
	for (register int i = 1; i < N; ++i)
		if (i != R)
			fac[i] = fac[i - 1] * 1ll * i % R;
		else
			fac[i] = fac[i - 1];
	// 特判：约分！
	p1[1] = (p[1] - 1) % R;
	p2[1] = p[1];
	// 计算 p1 和 p2 数组
	for (register int i = 2; i <= p[0]; ++i)
		p1[i] = p1[i - 1] * 1ll * (p[i] - 1) % R, p2[i] = p[i];
	// 将 p 数组中的元素进行逆元处理
	for (register int i = 1; i <= p[0]; ++i)
		if (p[i] != R)
			p[i] = quick_mod(p[i], R - 2, R);
	// 计算 p 数组的累积值
	for (register int i = 2; i <= p[0]; ++i)
		if (p[i] != R)
			p[i] = p[i] * 1ll * p[i - 1] % R;
		else
			p[i] = p[i - 1];
	// 处理每个测试用例
	while (T--) {
		// 读取 N 和 M
		register int n = in(), m = in();
		// 判断特殊情况
		if (m < R && R <= n) {
			puts("0");
			continue;
		}
		// 在 p2 数组中查找小于等于 m 的最大素数的索引
		register int id = std::upper_bound(p2 + 1, p2 + 1 + p[0], m) - (p2 + 1);
		// 根据 id 值判断输出结果
		if (id < 1)
			wr(fac[n]), putchar('\n');
		else
			wr(fac[n] * 1ll * p1[id] % R * 1ll * p[id] % R), putchar('\n');
	}
}

// 快速幂取模函数
inline int quick_mod(int a, int b, int c) {
	register int s = 1;
	while (b) {
		if (b & 1) s = (s * 1ll * a) % c;
		a = (a * 1ll * a) % c;
		b >>= 1;
	}
	return s;
}

// 素数筛选函数
inline void prime() {
	for (register int i = 2; i < N; ++i)
		if (!vis[i]) {
			p[++p[0]] = i;
			if (i * 1ll * i >= N) continue;
			for (register int j = i * i; j < N; j += i)
				vis[j] = 1;
		}
}

// 读取整数函数
inline int in() {
	register char c = getchar();
	register int x = 0, f = 1;
	// 处理负号
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	// 读取数字
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c & 15);
	return x * f;
}

// 输出整数函数
inline void wr(int x) {
	// 处理负号
	if (x < 0) putchar('-'), x = -x;
	// 递归输出
	if (x / 10) wr(x / 10);
	putchar(x % 10 + '0');
}

prean:

#include <cstdio>
#include <cstdint>
#include <algorithm>

// 读取整数
typedef __uint128_t L;
typedef unsigned long long ull;

// 最大范围定义
const int M = 1e7 + 5;

// 全局变量声明
int T, P, mx, top, n[10005], m[10005], pri[M], phi[M], fac[M], ifac[M];
bool zhi[M];

// 快速幂取模结构体定义
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
	friend inline ull operator%(const ull &a, const FastMod &mod) {
		ull q = (L(mod.m) * a) >> 64;
		ull r = a - q * mod.b;
		return r >= mod.b ? r - mod.b : r;
	}
} mod(2);

// 主函数
signed main() {
	// 变量声明
	register int i, j, x;
	// 读取测试用例数和模数
	scanf("%d%d", &T, &P);
	// 初始化数组
	phi[1] = fac[1] = ifac[1] = 1;
	mod = FastMod(ull(P));

	// 读取测试用例中的 n 和 m，同时记录最大值
	for (i = 1; i <= T; ++i)
		scanf("%d%d", n + i, m + i), mx = n[i] > mx ? n[i] : mx, mx = m[i] > mx ? m[i] : mx;

	// 素数筛选
	for (i = 2; i <= mx; ++i) {
		if (!zhi[i])
			pri[++top] = i, phi[i] = 1;
		for (j = 1; j <= top && (x = i * pri[j]) <= M; ++j) {
			zhi[x] = true;
			if (!(i % pri[j]))
				break;
		}
		phi[i] = i - phi[i];
	}

	// 计算 fac 和 ifac 数组
	for (i = 2; i <= mx; ++i) {
		if (i ^ P)
			fac[i] = 1ull * fac[i - 1] * i % mod, ifac[i] = 1ull * (P - P / i) * ifac[P % i] % mod;
		else
			fac[i] = fac[i - 1], ifac[i] = 1;
	}

	// 计算欧拉函数（phi）和逆元（ifac）数组
	for (i = 2; i <= mx; ++i)
		phi[i] = 1ull * phi[i - 1] * phi[i] % mod, ifac[i] = 1ull * ifac[i - 1] * ifac[i] % mod;

	// 处理每个测试用例并输出结果
	for (i = 1; i <= T; ++i)
		printf("%d\n", n[i] - n[i] % P == m[i] - m[i] % P ? 1ull * fac[n[i]] * ifac[m[i]] % mod * phi[m[i]] % mod : 0);
}

yhgalaxy:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;

#define Rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define RepD(i, r, l) for (int i = (r); i >= (l); --i)
#define RepG(i, x) for (int i = hd[x]; i; i = e[i].nxt)

typedef long long ll;

const int N = 10000005;

bool np[N]; // 用于素数筛选的标记数组
int mod, n, m, fac[N], phi[N], fac0[N], phi0[N];

// 快速幂取模
ll power(ll x, int n) {
    ll s = 1;
    while (n) {
        if (n & 1)
            (s *= x) %= mod;
        (x *= x) %= mod, n >>= 1;
    }
    return s;
}

int main() {
    int T, lim = 1e7;
    scanf("%d%d", &T, &mod);

    // 筛素数
    np[1] = 1;
    Rep(i, 2, lim)
        if (!np[i])
            for (int j = 2 * i; j <= lim; j += i)
                np[j] = 1;

    fac[0] = phi[0] = 1, fac0[0] = phi0[0] = 0;

    // 计算阶乘和欧拉函数的幂因子
    Rep(i, 1, lim) {
        int x = i, k = 0;

        // 分解质因数，统计幂因子
        while (x % mod == 0) x /= mod, ++k;

        fac[i] = 1ll * fac[i - 1] * x % mod, fac0[i] = fac0[i - 1] + k;

        // 对于素数，欧拉函数为 p - 1，对于合数，欧拉函数为 (p - 1) * p^(k-1)，其中 p 为质因数
        x = (np[i] ? i : i - 1), k = 0;
        while (x % mod == 0) x /= mod, ++k;
        phi[i] = 1ll * phi[i - 1] * x % mod, phi0[i] = phi0[i - 1] + k;
    }

    while (T--) {
        scanf("%d%d", &n, &m);
        ll ans = 1ll * fac[n] * phi[m] % mod * power(fac[m], mod - 2) % mod;

        // 特判，如果幂因子不一致则答案为0
        if (fac0[n] + phi0[m] - fac0[m])
            ans = 0;

        printf("%lld\n", ans);
    }

    return 0;
}