luogu2155 [SDOI2008]沙拉公主的困惑

求出1到N的阶乘中与M的阶乘互质的数的个数，对R取模，多组询问，R<=10^9+10，T<=10000，1 < = N , M < = 10000000

1到\(M!\)中与\(M!\)互质的数显然为\(\varphi(M)\)，由于\(N!\)是\(M!\)的倍数，所以一共有\(\frac {N!}{M!}\)组数，每组数都有\(\varphi(M)\)个数字与\(M!\)互质，所以答案为\(\frac{N!}{M!}\varphi(M!)\)

根据\(\varphi\)的计算式，枚举\(M!\)所有素数计算即可，即1_{M的素数，显然可以预处理，设n=10000000，由于1}n内素数为\(\frac{n}{\ln n}\)个，而每个素数由于需要计算逆元，需要时间为\(O(\log n)\)，总复杂度为\(O(n)\)，预处理阶乘每次询问直接乘即可，询问复杂度\(O(1)\)，预处理复杂度\(O(n)\)

#include <cstdio>

using namespace std;

bool vis[10000010];

int prime[10000010], tot, fuck = 10000000;

int prod[10000010], p;

int fac[10000010];

int qpow(int x, int y)

{

	int res = 1;

	for (x %= p; y > 0; y >>= 1, x = x * (long long)x % p) if (y & 1) res = res * (long long)x % p;

	return res;

}

int main()

{

	int t; scanf("%d%d", &t, &p);

	prod[1] = fac[1] = fac[0] = 1;

	for (int i = 2; i <= fuck; i++)

	{

		if (vis[i] == false) prime[++tot] = i, prod[i] = (i - 1) * (long long)qpow(i, p - 2) % p;

		else prod[i] = 1;

		for (int j = 1; j <= tot && i * prime[j] <= fuck; j++)

		{

			vis[i * prime[j]] = true;

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

		}

		prod[i] = prod[i] * (long long)prod[i - 1] % p;

		fac[i] = i * (long long)fac[i - 1] % p;

	}

	while (t --> 0)

	{

		int n, m;

		scanf("%d%d", &n, &m);

		printf("%d\n", (int)(fac[n] * (long long)prod[m] % p));

	}

	return 0;

}

38行一遍A

upd:观察了pinkrabbit的题解，发现这么写是错的，对于n>=r的情况，n中的因子r可能会和phi中的逆元消掉(phi中因子没有逆元的假象掩盖了事实)

解决方法类似扩展卢卡斯，记录成\(x*y^b\)的形式。不过感觉出题人不会弄成这么毒瘤，除了你谷的管理员加强数据，就不改了，长个记性就行。。。真相：由于懒癌

巴特西

luogu2155 [SDOI2008]沙拉公主的困惑

最新文章

热门文章