NSOqwq

题解 CF1114F 【Please, another Queries on Array?】

CF1114F Please, another Queries on Array?


Part 0 有趣的事情

  • 这题我在做的时候某处 $l$ 和 $r$ 写反了,调了两个多小时。
  • 你需要有足够的耐心等待本题评测结束,本题共有 $100$ 个测试点,每个测试点 $3$ 秒左右。

那就开始吧!


Part 1 题意简述

给定一个数列、两种操作。第一种操作,对 $[l, r]$ 内的所有数同乘以 $m$;第二种操作,求出 $\varphi(\prod\limits_{i=l}^{r}a_i) \bmod 1000000007$ 的值。


Part 2 题目分析

由区间修改、查询想到线段树。

区间乘是很常见的一种线段树操作,但 求区间积的欧拉函数 比较难处理。


难点 1: 如何求欧拉函数

作为一个啥数论都不会的菜鸡,我看了一下欧拉公式的定义:

$\varphi(n)$ 为 $1\dots n$ 中与 $n$ 互质的数的个数。

而随便 bdfs 即可得到欧拉公式的求法:

$$\varphi(x)=x\cdot\prod_{i=1}^n(\dfrac{p_i-1}{p_i})\ (p_1, p_2, \dots p_n \text{为 } x \text{ 的所有质因数})$$

因为计算过程中,$x$ 需要取模,最终得到的 $x$ 并不是原来的 $x$,不能保证 $p$ 一定能被 $x$ 整除。所以后面的每个 $\dfrac{p - 1}{p}$ 需要提前进行计算,当进行查询操作的时候直接使用。这就是一个有理数取模的问题了,不了解的可以转到 P2613


难点 2: 如何找出一个数的所有质因数

找出所有的质因数,才能进行欧拉函数的计算。

其实大体思路比较好想,就是除了区间乘积以外,线段树内再维护一些数据——区间乘积包括哪些质因数。具体实现的话,使用状态压缩的概念会比较容易。$300$ 内有 $62$ 个质数,而 $2^{62}$ 恰好在 long long 的范围内,所以可以把一个数的质因数的情况压缩到一个 long long 内(暂且叫这个数为“质因数状态”吧)。

当然,同时也需要维护一个相应的 lazytag。这一块代码实现比较复杂,一定不要把细节写错了。

Part 3 放进线段树板子里重新整理思路和注意点

初始化

  • 所有乘法 lazytag 为 1;
  • 所有质因数状态相关的变量全都设为 0。
  • 可以提前算好 $300$ 以内的质数。

update 操作

  • update 操作里,除了更新当前区间的乘积以外,还要更新其乘积所含的质因数状态;
  • 可以新加一个参数“质因数状态”,方便操作。

query 操作

  • query 操作需要返回一个线段树节点(因为计算欧拉函数时既需要用乘积也需要用质因数,不能只返回一个)

pushUp 操作

  • 父亲的乘积 $=$ 左儿子乘积 $\times$ 右儿子乘积;
  • 父亲的质因数状态 $=$ 左儿子质因数状态 按位或 右儿子质因数状态;

pushDown 操作

  • 子树的乘积乘以父亲的乘法 lazytag 的子树区间长度次方,子树的乘法 lazytag 乘以父亲的乘法 lazytag;
  • 子树的质因数状态和它的 lazytag 都按位或上父亲的质因数状态 lazytag;
  • 乘法的 lazytag 置 1,质因数状态的 lazytag 置 0。
  • 取模别忘了。

主程序

  • 需要提前预处理计算欧拉函数所需的值;
  • 进行修改操作之前,先找出乘上的那个数的所有的质因数,压缩成一个状态,传入 update 函数;
  • 进行查询操作之后,要算出欧拉函数的值。

Part 4 Code

#include <cstdio>
#define int long long
#define MOD 1000000007
int mi(int a, int b, int mo); // 快速幂,不贴代码了
int read(); // 快读,不贴代码了
int readOpt() { // 读操作类型(修改操作返回 1,查询操作返回 2)
    char ch = getchar(); int ans;
    while (ch < 'A' || ch > 'Z') ch = getchar();
    if (ch == 'T') return 2;
    else return 1;
}
struct Node {
    int val; int p;
    int lazy, lazyP;
    Node() { val = 1; lazy = 1; p = 0; lazyP = 0; }
} xds[1600007]; // 线段树结点
int n, q;
int a[1600007];
int f[1001], inv[1001];
int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293};
void pushUp(int x) {
    xds[x].val = xds[x * 2].val * xds[x * 2 + 1].val % MOD;
    xds[x].p = xds[x * 2].p | xds[x * 2 + 1].p;
}
void pushDown(int x, int l, int m, int r) {
    // 更新子树乘积
    xds[x * 2].val = xds[x * 2].val * mi(xds[x].lazy, m - l + 1, MOD) % MOD;
    xds[x * 2 + 1].val = xds[x * 2 + 1].val * mi(xds[x].lazy, r - m, MOD) % MOD;
    // 更新子树乘法 lazytag
    xds[x * 2].lazy = xds[x * 2].lazy * xds[x].lazy % MOD;
    xds[x * 2 + 1].lazy = xds[x * 2 + 1].lazy * xds[x].lazy % MOD;
    // 更新子树质因数状态
    xds[x * 2].p |= xds[x].lazyP;
    xds[x * 2 + 1].p |= xds[x].lazyP;
    // 更新子树质因数状态 lazytag
    xds[x * 2].lazyP |= xds[x].lazyP;
    xds[x * 2 + 1].lazyP |= xds[x].lazyP;
    xds[x].lazy = 1;
    xds[x].lazyP = 0;
}
void build(int l, int r, int x) {
    if (l == r) {
        xds[x].val = a[l];
        for (int i = 0; i < 62; ++i)
            if (a[l] % prime[i] == 0)
                xds[x].p |= (1ll) << i; // 找出所有质因数
        return;
    }
    const int m = (l + r) >> 1;
    build(l, m, x * 2);
    build(m + 1, r, x * 2 + 1);
    pushUp(x);
}
void update(int x, int l, int r, int delta /* 乘上的数 */, int prime /* 即质因数状态 */, int cl, int cr) {
    if (cl > r || cr < l) return;
    if (l <= cl && cr <= r) {
        xds[x].val = xds[x].val * mi(delta, cr - cl + 1, MOD) % MOD;
        xds[x].lazy = xds[x].lazy * delta % MOD;
        xds[x].p |= prime;
        xds[x].lazyP |= prime;
        return;
    }
    const int m = (cl + cr) >> 1;
    pushDown(x, cl, m, cr);
    update(x * 2, l, r, delta, prime, cl, m);
    update(x * 2 + 1, l, r, delta, prime, m + 1, cr);
    pushUp(x);
}
Node query(int x, int l, int r, int cl, int cr) {
    if (cl > r || cr < l) return Node();
    if (l <= cl && r >= cr) { return xds[x]; }
    const int m = (cl + cr) >> 1;
    pushDown(x, cl, m, cr);
    Node n; Node ll = query(x * 2, l, r, cl, m); Node rr = query(x * 2 + 1, l, r, m + 1, cr);
    n.val = ll.val * rr.val % MOD;
    n.p = ll.p | rr.p;
    return n;
}
signed main() {
    n = read(), q = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    build(1, n, 1);

    // 计算每个 (p - 1) / p 的结果
    inv[1] = 1;
    for (int i = 2; i <= 300; ++i)
        inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
    for (int i = 0; i < 62; ++i)
        f[i] = inv[prime[i]] * (prime[i] - 1) % MOD;

    for (int i = 1; i <= q; i += 1) {
        int opt = readOpt(), x = read(), y = read();
        if (opt == 1) {
            int k = read();
            int t = 0;
            for (int i = 0; i < 62; ++i)
                if (k % prime[i] == 0)
                    t |= (1ll) << i; // 找出所有质因数
            update(1, x, y, k, t, 1, n);
        } else {
            Node ans = query(1, x, y, 1, n);
            // 算欧拉函数
            int phi = ans.val;
            for (int i = 0; i < 62; ++i) {
                if (ans.p >> i & 1) {
                    phi = phi * f[i] % MOD;
                }
            }
            printf("%lld\n", phi % MOD);
        }
    }
    return 0;
}

2021-05-02 21:35:39 in 题解