题解 P6217【简单数论题】
Daniel13265
·
·
题解
# 题意
给出正整数序列 $a$，多次给出 $l,r,x$ 询问 $\prod_{i=l}^r\operatorname{lcm}(a_i,x)$。
# 分析
观察到
$$\prod_{i=l}^r\operatorname{lcm}(a_i,x)=\frac{x^{r-l+1}\prod_{i=l}^ra_i}{\prod_{i=l}^r\gcd(a_i,x)}$$
明显 $x^{r-l+1}\prod_{i=l}^ra_i$ 可以维护前缀积并使用快速幂求出，于是我们只需要求 $\prod_{i=l}^r\gcd(a_i,x)$ 的值即可。
如果将 $a_i$ 和 $x$ 分别作质因数分解：
$$\begin{aligned}a_i&=\prod_{j=1}^kp_j^{q_{ij}}\\x&=\prod_{j=1}^kp_j^{q_{xj}}\end{aligned}$$
其中 $p_j$ 表示第 $j$ 个质数，$q\in\mathbb N$。那么有
$$\begin{aligned}\prod_{i=l}^r\gcd(a_i,x)&=\prod_{i=l}^r\prod_{j=1}^kp_j^{\min(q_{ij},q_{xj})}\\&=\prod_{i=1}^kp_i^{\sum_{j=l}^r\min(q_{ji},q_{xi})}\\&=\prod_{i=1}^kp_i^{\sum_{t=1}^{q_{xi}}\sum_{j=l}^r[t\le q_{ji}]}\\&=\prod_{i=1}^kp_i^{\sum_{t=1}^{q_{xi}}\sum_{j=l}^r\left[p_i^t\small|\scriptsize p_i^{q_{ji}}\right]}\\&=\prod_{i=1}^kp_i^{\sum_{t=1}^{q_{xi}}\sum_{j=l}^r\left[p_i^t\small|\scriptsize a_j\right]}\end{aligned}$$
所以我们需要分别对每一个能够整除 $x$ 的质数正整数幂，求出它能够整除 $a_l,a_{l+1},\ldots,a_r$ 中的多少个数，将底数相同的幂的个数相加后快速幂求积即为需要求的部分。
如果线性筛预处理小于 $\sqrt x$ 的质数，那么枚举 $p_i$ 的复杂度为
$$\mathcal O\left(\pi\left(\sqrt x\right)\right)\leq\Theta\left(\frac{\sqrt x}{\log\sqrt x}\right)=\Theta\left(\frac{\sqrt x}{\log x}\right)$$
设能整除一个数 $x$ 的所有质数正整数幂形成的集合为 $\operatorname{PP}(x)$。考虑到对于任意质数 $p\ge2$，有
$$\big|\operatorname{PP}(x\times p)\big|=\big|\operatorname{PP}(x)\big|+1$$
因而
$$\mathcal O\left(\big|\operatorname{PP}(x)\big|\right)=\mathcal O(\log x)$$
因此求出 $\operatorname{PP}(x)$ 的总复杂度为
$$\Theta\left(\frac{\sqrt x}{\log x}\right)+\mathcal O(\log x)=\Theta\left(\frac{\sqrt x}{\log x}\right)$$
可以先对于每一个 $a_i$ 求出 $\operatorname{PP}(a_i)$，之后将每一个质数的正整数幂与包含它的集合对应。这样，对于每一个询问的 $x$，可以在 $\mathcal O(\log n)$ 的时间复杂度内二分查找到 $l,r$ 在能够被整除 $x$ 的一个质数正整数幂整除的 $a_i$ 的下标 $i$ 的集合中的位置，进一步计算出该质数正整数幂在 $\operatorname{PP}(a_l),\operatorname{PP}(a_{l+1}),\ldots,\operatorname{PP}(a_r)$ 中出现的次数。
对每一个质数的正整数幂作二分的时间复杂度都是 $\mathcal O(\log n)$，共有 $\mathcal O(\log x)$ 个这样的质数正整数幂，故此部分的复杂度为 $\mathcal O\left(\log x\log n\right)$。从而得到这个做法的总空间复杂度为 $\mathcal O(\sqrt a+n\log a)$，总时间复杂度为
$$\Theta\left(n\frac{\sqrt a}{\log a}\right)+\mathcal O\left(q\pi\left(\sqrt a\right)\right)+\mathcal O\left(q\log x\log n\right)\leq\Theta\left(n\frac{\sqrt a}{\log a}+q\frac{\sqrt a}{\log a}+q\log x\log n\right)$$
如果认为 $n,q,a_i,x\sim N$，则总复杂度为 $\Theta\left(\frac{N\sqrt N}{\log N}\right)\sim\Theta\left(\frac{\sqrt N}{\log N}\right)\sim\mathcal O(N\log N)$。
更优的做法是在线性筛的时候记录筛去每一个数的质数，这个质数就一定是该数的最小质因子。于是对于任意一个数，可以通过不断除以它的最小质因子来得到它的所有的质因子。由于每一次除都这个数都要至少减少一半，所以利用这个方法求 $\operatorname{PP}(x)$ 的时间复杂度是 $\mathcal O(\log x)$。总空间复杂度为 $\mathcal O(\max(a,x)+n\log a)$，总时间复杂度为
$$\mathcal O\left(\max(a,x)+n\log a\right)+\mathcal O\left(q\log x\right)+\mathcal O\left(q\log x\log n\right)=\mathcal O\left(\max(a,x)+n\log a+q\log x\log n\right)$$
如果认为 $n,q,a_i,x\sim N$，则总复杂度为 $\mathcal O\left(N\log N\right)\sim\mathcal O\left(\log^2N\right)\sim\mathcal O(N\log N)$。
# 参考代码
```cpp
mul[0] = 1;
for (int i = 1; i <= n; ++i) {
int t = read();
mul[i] = mul[i - 1] * t % P;
while (~-t) {
const int &p = fir[t];
int tmp = 1;
while (!(t % p)) {
t /= p;
tmp *= p;
vc[tmp].push_back(i);
}
}
}
while (q--) {
const int &l = read(), &r = read(), &x = read();
int t = x;
long long res = 1ll;
while (~-t) {
const int &p = fir[t];
int tmp = 1, tot = 0;
while (!(t % p)) {
t /= p;
tmp *= p;
tot += upper_bound(vc[tmp].begin(), vc[tmp].end(), r) - lower_bound(vc[tmp].begin(), vc[tmp].end(), l);
}
res = res * qpow(p, tot) % P;
}
cout << (mul[r] * qpow(mul[l - 1] * res % P, P - 2) % P * qpow(x, r - l + 1) % P) << '\n';
}
```