题面

传送门

Sol

题目要求\(\sum_{i=1}^{n!}[gcd(i, m!)==1]\)

设\(N=n!，M=m!\)，莫比乌斯反演一波

就变成了\(\sum_{d|M}\mu(d)\frac{N}{d}\)

因为\(M|N\)所以\(d|N\)

而有个定理\(\sum_{d|M}\frac{\mu(d)}{d}=\frac{\varphi(M)}{M}\)

那么就是求\(\frac{\varphi(M)}{M}*N\)

就是\(\varphi(m!)*\frac{n!}{m!}\)

而\(\varphi(m!)=\varphi(m)*(m-1)!\)

化简

那就变成SB题了

预处理就好了

# include <bits/stdc++.h>

# define IL inline

# define RG register

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

const int _(1e7 + 1);

IL ll Read(){

	RG char c = getchar(); RG ll x = 0, z = 1;

	for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

	for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

	return x * z;

}

int n, m, Zsy, prime[_], num, fac[_], inv[_], id[_];

bool isprime[_];

IL int Pow(RG ll x, RG ll y){

	RG ll ret = 1;

	for(; y; y >>= 1, x = x * x % Zsy) if(y & 1) ret = ret * x % Zsy;

	return ret;

}

IL void Sieve(){

	isprime[1] = 1; fac[1] = 1;

	for(RG int i = 2; i < _; ++i){

		if(!isprime[i]) prime[++num] = i , inv[num] = Pow(i, Zsy - 2);

		for(RG int j = 1; j <= num && i * prime[j] < _; ++j){

			isprime[i * prime[j]] = 1;

			if(!(i % prime[j])) break;

		}

		fac[i] = 1LL * fac[i - 1] * i % Zsy;

	}

	for(RG int i = 1; i < num; ++i)

		for(RG int j = prime[i]; j < prime[i + 1]; ++j) id[j] = i;

	inv[0] = prime[0] = 1;

	for(RG int i = 1; i <= num; ++i){

		prime[i] = 1LL * (prime[i] - 1) * prime[i - 1] % Zsy;

		inv[i] = 1LL * inv[i] * inv[i - 1] % Zsy;

	}

}

IL int Calc(){  return 1LL * fac[n] * prime[id[m]] % Zsy * inv[id[m]] % Zsy; }

int main(RG int argc, RG char* argv[]){

	RG int T = Read(); Zsy = Read();

	Sieve();

	while(T--){

		n = Read(); m = Read();

		printf("%d\n", Calc());

	}

	return 0;

}