luogu2155 [SDOI2008]沙拉公主的困惑

link

求出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
", (int)(fac[n] * (long long)prod[m] % p));
	}
	return 0;
}

38行一遍A

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

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