求出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!\)所有素数计算即可，即1n内素数为\(\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\)的形式。不过感觉出题人不会弄成这么毒瘤，除了你谷的管理员加强数据，就不改了，长个记性就行。。。真相：由于懒癌