题意

给定 n 个数 a_{1\cdots n},进行 q 次单点乘法操作,满足 1\le n,q,a_i\le 2\times 10^5,求每次操作完后 \displaystyle\gcd_{i = 1}^na_i\bmod (10^9 + 7)

题解

讲讲我的考场思路。

我们知道 gcd 实际上就是所有的质因子取最小次数再乘起来,想到这里就很自然的去维护所有的质因子的次数。

对每种出现的质因子用一个数据结构来维护其次数,支持单点修改和最值查询,我这里使用的是动态开点线段树(避免普通线段树的空间浪费)(当然其他支持删除并求最值的数据结构也是可以的比如可删堆,std::map 等等),因为 2\times 10^5 中素数的个数约为 \dfrac{n}{\ln n}\approx 20113 个,而一个 a_i 中最多有 7 个互异质因子,所以大概估计一下发现不会炸。

然后就很简单了。一开始输入数列的时候直接把质因子 p_j 对应的线段树在位置 i 上加上对应的次数 k 即可,注意这个线段树维护的是最小值(因为这样就可以方便的求 gcd),不难发现 gcd 中这个质因子贡献的值为 p_j^{\min\lbrace k\rbrace},即树根的值。

维护 gcd 的时候乘上 p_j^{k_0} 的逆元以先消掉质因子 p_j 产生的贡献,修改完了再把 p_j^{k_0′} 乘回去就可以了。

根据上述过程知复杂度为 O(n\log^2n),可以通过本题

#include <cstdio>
#include <cctype>
#include <set>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)

int read()
{
    int s = 0, x = 0;
    char c = getchar();
    while (!isdigit(c))
        x |= (c == '-'), c = getchar();
    while (isdigit(c))
        s = s * 10 + c - '0', c = getchar();
    return x ? -s : s;
}

typedef long long ll;
inline int min(int a, int b) {return a < b ? a : b;}

const int maxn = 2e5 + 5, mod = 1e9 + 7;
int a[maxn], n, q;
int p[maxn], isp[maxn], tot, minfact[maxn];

ll qpow(ll base, ll p = mod - 2)
{
    ll ret = 1;
    for (; p; p >>= 1)
    {
        if (p & 1)
            ret = ret * base % mod;
        base = base * base % mod;
    }
    return ret;
}

void make_prime()
{
    FOR(i, 2, maxn - 2)
    {
        if (!isp[i])
            p[++tot] = i, minfact[i] = tot;
        for (int j = 1; i * p[j] < maxn; ++j)
        {
            isp[i * p[j]] = 1;
            minfact[i * p[j]] = j;//维护一个数的最小质因子以再在分解时避免遍历无用的质数
            if (i % p[j] == 0) break;
        }
    }
    return;
}

const int maxp = 2e7 + 5;//空间往不会炸的卡是绝对没错的
int cnt, lson[maxp], rson[maxp], val[maxp];//动态开点线段树
int root[maxn];

void modify(int &now, int l, int r, int x, int add)
{
    if (!now)
        now = ++cnt;
    if (l == r)
    {
        val[now] += add;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
        modify(lson[now], l, mid, x, add);
    else modify(rson[now], mid + 1, r, x, add);
    val[now] = min(val[lson[now]], val[rson[now]]);
    return;
}

int main()
{
    make_prime();
    n = read(), q = read();
    ll gcd = 1;
    FOR(i, 1, n)
    {
        int tmp = read();
        for (int j = minfact[tmp]; tmp > 1;)//j 的初始值要是最小质因子,避免无谓的循环
        {
            int k = 0;
            while (tmp > 1 && tmp % p[j] == 0)
                ++k, tmp /= p[j];
            gcd = gcd * qpow(qpow(p[j], val[root[j]])) % mod;//首先 gcd 删除 p[j] 的贡献
            modify(root[j], 1, n, i, k);
            gcd = gcd * qpow(p[j], val[root[j]]) % mod;//然后把贡献乘回去
            if (tmp > 1) j = minfact[tmp];//如果不这么写是会 FST 的
        }
    }
    while (q--)
    {
        int x = read(), v = read();
        for (int j = minfact[v]; v > 1;)
        {
            while (v > 1 && v % p[j]) ++j;
            int k = 0;
            while (v > 1 && v % p[j] == 0)
                ++k, v /= p[j];
            gcd = gcd * qpow(qpow(p[j], val[root[j]])) % mod;
            modify(root[j], 1, n, x, k);
            gcd = gcd * qpow(p[j], val[root[j]]) % mod;
            if (v > 1) j = minfact[v];
        }
        printf("%lld\n", gcd);
    }
    return 0;
}
最后修改日期: 2021年3月7日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。