P5655 基础数论函数练习题

· · 题解

考虑预处理出每个区间的答案，记作：

A(l,r) = \operatorname{lcm}_{i = l}^{r} \{ a_i \}.

考虑对于每一个右端点 r，从右往左依次推出 A(r,r) \sim A(1,r)。

显然 A(1,r) \sim A(r,r) 单调不增。

设 b(i,r) 为 a_i 对 A(i,r) 的贡献：

\begin{cases} a_r, & i = r,\\ \\ \dfrac{A(i,r)}{A(i+1,r)} & i \in [1, r-1]. \end{cases}

问题转化为求所有 b(i,r)。

由 b 的定义有：

A(l,r) = \prod\limits_{i = l}^{r} b(i,r).

对于 i \in [1,r-1]，考虑用 A(i+1,r) 计算 A(i,r)：

\begin{aligned} A(i,r) &= \operatorname{lcm}(a_i, A(i+1,r))\\ &= \frac{a_i \cdot A(i+1,r)}{\gcd(a_i, A(i+1,r))}\\ &= \frac{a_i \cdot A(i+1,r)}{\gcd \left( a_i, \prod\limits_{j = i + 1}^{r} b(j,r) \right)}. \end{aligned}

显然有：

b(i,r) = \frac{a_i}{\gcd \left( a_i, \prod\limits_{j = i + 1}^{r} b(j,r) \right)}.

从右到左依次推出 b(i,r)。由于 \displaystyle\prod\limits_{j = i + 1}^{r} b(j,r) 很大，可以将其对 a_i 取模。于是我们得到了一个 \mathcal{O}(n^3) 的做法。

考虑优化 b(i,r) 的计算。

假设已经计算出了 b(1,r) \sim b(r,r)。考虑右端点从 r 推到 r+1 时，如何由 b(1,r) \sim b(r,r) 推出 b(1,r+1) \sim b(r,r+1)。

显然 A(i+1,r) \mid A(i+1,r+1)。于是 b(i,r+1) \mid b(i,r)。

考虑边界：b(r,r) = a_r，b(r,r+1) = \dfrac{a_r}{\gcd(a_r,a_{r+1})}，满足 b(r,r+1) \mid b(r,r)。

设 d(i,r+1) = \dfrac{b(i,r)}{b(i,r+1)}。问题转化为求所有 d(i,r+1)。

设：

\begin{aligned} A(i,r) &= \prod\limits_{p} p^{\mathscr{A}(p,i,r)},\\ a_{r+1} &= \prod\limits_{p} p^{\alpha(p,r+1)},\\ b(i,r) &= \prod\limits_{p} p^{\beta(p,i,r)},\\ d(i,r+1) &= \prod\limits_{p} p^{\delta(p,i,r+1)}. \end{aligned}

其中 p 为质数。

由 d 的定义，有：

\delta(p,i,r+1) = \beta(p,i,r) - \beta(p,i,r+1).

显然 b(i,r) \rightarrow b(i,r+1) 的变化量 d(i,r+1) 可以通过考察 \beta(p,i,r) \rightarrow \beta(p,i,r+1) 的变化量 \delta(p,i,r+1) 得到。

而 \beta(p,1,r) \sim \beta(p,r,r) 即 \mathscr{A}(p,1,r) \sim \mathscr{A}(p,r,r) 的后缀差分数组。

注意到加入 a_{r+1} 的过程实际上就是令：

\mathscr{A}(p,i,r+1) = \max( \mathscr{A}(p,i,r), \alpha(p,r+1) ).

作用在后缀差分数组 \beta 上，考察 \beta 的变化值 \delta：

\delta(p,i,r+1) = \min \left( \beta(p,i,r), \alpha(p,r+1) - \sum\limits_{j = i + 1}^{r} \delta(p,j,r+1) \right).

宏观上：

d(i,r+1) = \gcd \left( b(i,r), \frac{a_{r+1}}{\prod\limits_{j = i + 1}^{r} d(j,r+1)} \right).

从右到左依次推出 d(r,r+1) \sim d(1,r+1) 即可。时间复杂度 \mathcal{O}(n^2 \log V)。总复杂度 \mathcal{O}(T(n^2 \log V + Q) )。

:::info[Code]{open}

#include <bits/stdc++.h>
#define int long long

const int N = 310;

const int TT = 1e9 + 7;

using namespace std;

int T;

int n, q;

int a[N];

int b[N];

int A[N][N];

inline int read() {
    int ret = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        ret = ret * 10 + (ch & 15), ch = getchar();
    return ret * f;
}

inline int gcd(int x, int y) {
    if (!x)
        return y;
    if (!y)
        return x;
    int t = __builtin_ctzll(x | y);
    x >>= __builtin_ctzll(x);
    while (y) {
        y >>= __builtin_ctzll(y);
        if (x > y)
            swap(x, y);
        y -= x;
    }
    return x << t;
}

void _solve() {
    n = read(), q = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    for (int r = 1; r <= n; r++) {
        A[r][r] = a[r] % TT;
        b[r] = a[r];
        int prod_d = 1;
        for (int i = r - 1; i >= 1; i--) {
            int d_i = gcd(b[i], a[r] / prod_d);
            prod_d *= d_i;
            b[i] /= d_i;
        }
        for (int i = r - 1; i >= 1; i--)
            A[i][r] = A[i + 1][r] * (b[i] % TT) % TT;
    }
    while (q--) {
        int l = read(), r = read();
        printf("%lld\n", A[l][r]);
    }
}

signed main() {
    T = read();
    while (T--)
        _solve();
    return 0;
}

:::