[BZOJ 2186] [SDOI 2008] 沙拉公主的困惑

Description

大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为 \(1\) 到 \(N\) 的阶乘，但是，政府只发行编号与 \(M!\) 互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对 \(R\) 取模后的答案即可。\(R\) 是一个质数。

Input

第一行为两个整数 \(T,R~(R\le10^9+10,T\le10000)\)，\(T\) 表示该组中测试数据数目，\(R\) 为模；

后面 \(T\) 行，每行一对整数\(N,M\)，见题目描述。

Output

共 \(T\) 行，对于每一对 \(N,M\)，输出 \(1\) 至 \(N!\) 中与 \(M!\) 素质的数的数量对 \(R\) 取模后的值。

Sample Input

1 11

4 2

Sample Output

HINT

\(1 \le M\le N \le 10000000\)

Solution

因为 \(m\le n\Rightarrow m!\mid n!\)，所以答案为 \(\dfrac{\varphi(m!)\times n!}{m!}\)。

其中 \(\varphi(m!)=m!\left(1-\dfrac{1}{p_1}\right)\left(1-\dfrac{1}{p_2}\right)\left(1-\dfrac{1}{p_3}\right)\cdots\)，\(p_1,p_2,p_3\) 是 \(m!\) 的质因数，也就是 \([1,m]\) 中的质数。

最终 \(ans=\dfrac{\varphi(m!)\times n!}{m!}=n!\left(1-\dfrac{1}{p_1}\right)\left(1-\dfrac{1}{p_2}\right)\left(1-\dfrac{1}{p_3}\right)\cdots\)

Code

#include <cstdio>

#include <cmath>

const int N = 10000000;

int np[N + 5], p[N + 5], tot, inv[N + 5], fac[N + 5], ans[N + 5], mod;

int read() {

	int x = 0; char c = getchar();

	while (c < '0' || c > '9') c = getchar();

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

	return x;

}

void euler() {

	for (int i = 2; i <= N; ++i) {

		if (!np[i]) p[++tot] = i;

		for (int j = 1; j <= tot && i * p[j] <= N; ++j) {

			np[i * p[j]] = 1;

			if (i % p[j] == 0) break;

		}

	}

}

int main() {

	int T = read(); mod = read(), euler(), fac[1] = inv[1] = ans[1] = 1;

	for (int i = 2; i <= N; ++i) fac[i] = 1LL * fac[i - 1] * i % mod;

	for (int i = 2; i <= N && i < mod; ++i) inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;

	for (int i = 2; i <= N; ++i) {

		ans[i] = ans[i - 1];

		if (!np[i]) ans[i] = 1LL * ans[i] * (i - 1) % mod * inv[i % mod] % mod;

	}

	while (T--) {

		int n = read(), m = read();

		printf("%lld\n", 1LL * fac[n] * ans[m] % mod);

	}

	return 0;

}

巴特西