这道题的题解来自紫书，这里就写一下加深影响
给出N、M满足M <= N求出2-N!中存在多少个x使得x所有的素因子大于M，那么所有素因子大于M等价于与M!互素，根据欧几里得算法，
我们将x与M!互素转换成x%M!与M!互素，所以这样我们仅需要枚举小于M!的数，然后得到的个数*N!/M!(意思是说增加多少个M!仍然满足条件)，对于求出小于M!的数与M!互素，我们采用欧拉函数就是
，然后用phifac(n)=phi(n!)表示，我们能够发现phifac(n)与phifac(n-1)的关系，他们的素因子往往会相同，如果n不是素数，phifac(n) = phifac(n-1) * n否则phifac(n) = phifac(n-1) * (n-1)
这样就得到了phifac(n)的大小了，注意溢出，有些细节我并不是特别的清楚，下面是代码：
// UVa 11440 #include <cstdio> #include <cstring> #include <cmath> using namespace std; const int maxn = 10000000 + 5; const int MOD = 100000007; int vis[maxn], phifac[maxn]; void Eratosthenes(int n) { memset(vis, 0, sizeof(vis)); int m = sqrt(n + 0.5); for (int i = 2; i <= m; ++i) for (int j = i*i; j <= n; j += i) vis[j] = 1; } int main() { int n, m; Eratosthenes(10000001); phifac[1] = phifac[2] = 1; for (int i = 3; i <= 10000001; ++i) phifac[i] = (long long)phifac[i-1] * (vis[i] ? i : i-1) % MOD; while (scanf("%d%d", &n, &m) == 2 && n) { int ans = phifac[m]; for (int i = m+1; i <= n; ++i) ans = (long long)ans * i % MOD; printf("%d\n", (ans-1+MOD)%MOD); } return 0; }
原文：https://www.cnblogs.com/yifeiWa/p/11454999.html