题解 SP22412 【DIVFACT3 - Divisors of factorial (hard)】
Warriors_Cat
2020-12-24 13:09:08
$upd\ on \ 2021.2.13$ 修正了个小笔误。
---
[题面传送门](https://www.luogu.com.cn/problem/SP22412)。
> 题意：$T$ 组询问，每次给定 $n, m$，求 $n!$ 因子个数对 $m$ 取模的值，$n, m \le 10^8$。
算是个较为好想的题？
---
### $Solution:$
我们令：
$$n! = \prod_{i=1}^kp_i^{\alpha_i}$$
显然因子个数 $d(n!)$ 就为：
$$\prod_{i=1}^k(\alpha_i + 1)$$
对 $n!$ 这个数来说，显然有：
$$\alpha_k = \sum_{i=1}^{\left\lfloor\log_{p_k}n\right\rfloor}\left\lfloor\dfrac{n}{{p_k}^i}\right\rfloor$$
发现对于 $p_k > \sqrt{n}$ 的所有 $p_k$，其贡献只能有 $\left\lfloor\dfrac{n}{p_k}\right\rfloor$，可以用数论分块来搞。对于一个块 $(L, R)$，其贡献为 $\left\lfloor\dfrac{n}{L}\right\rfloor^{f_R - f_{L-1}}$，其中 $f_i$ 表示 $1$ 到 $i$ 中质数的个数。
对于 $p_k \le \sqrt{n}$ 的所有 $p_k$ 仍然考虑暴力。再套上线性筛 $10^8$ 以内的 $f$ 函数即可。
over，时间复杂度为 $O(N + T\sqrt{N})$。
---
### $Code:$
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define int long long
#define ull unsigned long long
#define fi first
#define se second
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1
#define y0 y_csyakioi_0
#define y1 y_csyakioi_1
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define per(i, x, y) for(int i = x; i >= y; --i)
#define repn(i, x, y, z) for(int i = x; i <= y; i += z)
#define pern(i, x, y, z) for(int i = x; i >= y; i -= z)
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 100000010;
int n, m, pri[N], len, f[N];
inline int fpow(int x, int p, int mod){ int ans = 1; for(; p; p >>= 1, x = x * x % mod) if(p & 1) ans = ans * x % mod; return ans; }
inline void sieve(int n){
f[0] = f[1] = 1;
rep(i, 2, n){
if(!f[i]) pri[++len] = i;
rep(j, 1, len){
if(i * pri[j] > n) break;
f[i * pri[j]] = 1;
if(i % pri[j] == 0) break;
}
}
rep(i, 1, n) f[i] = f[i - 1] + 1 - f[i];
}
inline int fac(int x, int y){ return x == 0 ? 0 : fac(x / y, y) + x / y; }
inline void work(){
n = read(); m = read(); int ans = 1, k = sqrt(n);
for(int i = 1; pri[i] <= k; ++i) ans = ans * (fac(n, pri[i]) + 1) % m;
for(int i = k + 1, j; i <= n; i = j + 1){
j = n / (n / i);
ans = ans * fpow(n / i + 1, f[j] - f[i - 1], m) % m;
}
printf("%lld\n", ans);
}
signed main(){ int qwq = read(); sieve(N - 10); while(qwq--) work(); return 0; }
```