Luogu P2155 [SDOI2008]沙拉公主的困惑

题目描述

https://www.luogu.com.cn/problem/P2155

Solution

注意到 $n\ge m$，$1$ 到 $n!$ 中与 $m!$ 互素的数的个数为 $\frac{n!}{m!}\varphi(m!)$

化简得到 $n!\prod_{i=1}^k\frac{p_i-1}{p_i}$

另外注意到当 $m<mod\le n$ 时，答案一定为 $0$

当 $mod<m$ 时，答案不一定为 $0$，因为 $n!$ 中的 $mod$ 和 $p_i$ 中的 $mod$ 消掉了

#include <iostream>
#include <cstdio>
#define maxn 10000010
#define ll long long
using namespace std;

int n, m, p;

bool isp[maxn]; int pri[maxn], cnt;
void init_isp(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) break; 
        } 
    } 
} 

ll fac[maxn], inv[maxn], phi[maxn]; 
void init(int n) {
    init_isp(n);
    fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * (i == p ? 1 : i) % p;
    inv[1] = 1; for (int i = 2; i <= n && i < p; ++i) inv[i] = -(p / i) * inv[p % i] % p;
    phi[1] = 1; inv[0] = 1; 
    for (int i = 2; i <= n; ++i) {
        phi[i] = phi[i - 1];
        if (!isp[i]) phi[i] = phi[i] * (i - 1) % p * inv[i % p] % p; 
    }
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T >> p; init(10000000); 
    while (T--) {
        cin >> n >> m;
        if (m < p && p <= n) cout << "0\n";
        else cout << ((fac[n] * phi[m] % p) + p) % p << "\n";
    }
    return 0;
}