自动搬运

查看原文

来自洛谷，原作者为

	Daniel13265 **

搬运于2025-08-24 22:18:39，当前版本为作者最后更新于2020-03-14 19:07:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\text{Upd. 2020/03/15}$：重写了部分内容使其更加易懂；修改了少量错别字；修正了少量公式错误。

题意

给出正整数序列 $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)$。

参考代码

  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';
  }