Siyuan

「Codeforces 594D」REQ
「Codeforces 594D」REQ
扫描右侧二维码阅读全文
02
2019/02

「Codeforces 594D」REQ

题目链接:Codeforces 594D

今天的数学课上,老师告诉 Vovochka 正整数的欧拉函数 $\varphi(n)$ 是计算小于等于 $n$ 且与 $n$ 互质的正整数的函数,$1$ 和任意正整数互质所以 $\varphi(1)=1$。

现在老师给了 Vovochka 一个数列 $a_1,a_2,\dots,a_n$,要求回答 $q$ 个询问 $l_i,r_i$,计算 $\varphi\left(\prod_{i=l}^r a_i\right)$ 的值,答案对 $10^9 + 7$ 取模。这个问题对二年级学生来说太难了,所以你决定帮助 Vovochka。

数据范围:$1 \le n,q \le 2 \times 10 ^ 5$,$1 \le a_i \le 10 ^ 6$。


Solution

由于只有询问操作,因此我们首先想到离线后用莫队解决。但是莫队的复杂度为 $\mathcal O(q\sqrt n\log a_i)$(其中 $\log a_i$ 指每个数的本质不同的质因子个数),显然无法通过本题(我卡了半个小时常数还是 $\text{TLE}$ 出题人毒瘤)。

还是考虑离线,我们将询问按照右端点排序,维护一个右指针,将每个 $a_i$ 逐个加入。用树状数组维护每个位置对答案的贡献。

我们考虑 $a_i$ 的其中一个质因子 $p$(其他的质因子同理)。由于我们把询问按照右端点排序了,而每个质因子只能对答案有一次贡献,那么我们把 $p$ 的贡献放到区间 $[1,i]$ 的最右边,即进行操作 $\text{add}(i, p - 1)$ 和 $\text{add}(i, p ^ {-1})$。如果 $p$ 已经出现过了,那么我们需要防止区间左端点左侧产生贡献,维护一个 $last_i$ 表示 $i$ 这个质因子上次出现的位置,将 $last_p$ 位置的贡献消去即可。

对于如何快速分解每个数的质因子,我们可以根据线性筛的本质:每个数只会被其最小质因子筛去,在筛的过程中直接记录每个数的最小质因子即可!

时间复杂度:$\mathcal O((n + q) \log n \log a_i)$。


Code

#include <cstdio>
#include <algorithm>

const int N = 2e5 + 5, M = 1e6 + 5;
const int P = 1e9 + 7;

int n, m, tot, a[N], b[N], p[M / 10], f[M], pre[N], lst[M], ans[N];
bool flg[M];

struct Data {
    int l, r, idx;
    bool operator<(const Data &b) const {
        return r < b.r;
    }
} q[N];

void sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!flg[i]) {
            p[++tot] = i, f[i] = i;
        }
        for (int j = 1; j <= tot && i * p[j] <= n; j++) {
            flg[i * p[j]] = true, f[i * p[j]] = p[j];
            if (i % p[j] == 0) break;
        }
    }
}
int pow(int x, int p) {
    int ans = 1;
    for (; p; p >>= 1, x = 1LL * x * x % P) {
        if (p & 1) ans = 1LL * ans * x % P;
    }
    return ans;
}
int inv(int x) {
    return pow(x, P - 2);
}
void add(int x, int v) {
    for (; x <= n; x += x & -x) b[x] = 1LL * b[x] * v % P;
}
int query(int x) {
    int ans = 1;
    for(; x; x ^= x & -x) ans = 1LL * ans * b[x] % P;
    return ans;
}
void update(int i) {
    for (int x = a[i], p = f[x]; x > 1; p = f[x]) {
        add(i, p - 1), add(i, inv(p));
        if (lst[p]) add(lst[p], inv(p - 1)), add(lst[p], p);
        lst[p] = i;
        while (x % p == 0) x /= p;
    }
}
int main() {
    scanf("%d", &n);
    pre[0] = 1;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        mx = std::max(mx, a[i]);
        pre[i] = 1LL * pre[i - 1] * a[i] % P;
    }
    sieve(mx);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].idx = i;
    }
    std::sort(q + 1, q + m + 1);
    for (int i = 0; i <= n; i++) b[i] = 1;
    for (int i = 1, j = 0; i <= m; i++) {
        int x = q[i].l, y = q[i].r;
        while (j < y) update(++j);
        ans[q[i].idx] = 1LL * pre[y] * inv(pre[x - 1]) % P * query(y) % P * inv(query(x - 1)) % P;
    }
    for (int i = 1; i <= m; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

发表评论