Codeforces Round 305 (Div. 1) C. Mike and Foam 容斥原理、质因数分解

题目链接

题目大意

有 $n$ 种啤酒，编号从 $1$ 到 $n$ 。第 $i$ 瓶啤酒上面有 $a_i$ 毫升的泡沫。

回答 $q$ 个查询。最初架子是空的。在每个操作中，给一个编号 $X$。如果编号为$X$的啤酒已经在架子上，应该从架子上取下它，否则他应该把它放在架子上。
每次询问后，输出该架子的分数。他们认为货架的分数是满足 $i<j$ 并且$gcd(a_i,a_j)=1$的数对$(i,j)$的个数。

$n$ 和 $q$（$1\le n$，$q\le 2\times {10}^5$），不同种类的啤酒数量和查询次数。

下一行包含$n$个由空格分隔的整数，$a_1,a_2,\dots ,a_n$($1\le a_i\le 5\times 10^5$ ），表示各种啤酒顶部的泡沫量。

接下来 $q$ 行一行包含一个查询。每个查询一个整数$X$（$1\le X\le N$），表示应从货架上添加或移除的啤酒的编号。

思路

考虑添加或移除走某个数之后 $ans$ 的变化量。

比如当前有 $k$ 个数，加入一个数 $x$ 只考对 $ans$ 增量，考虑容斥 $△=$$k-cnt(gcd$ $\ne$ $1)$ ，当 $k$ 中某个数与 $x$ 具有公共因子时 $gcd\ne 1$。

任意一个数 $n$ 都可以表示为 $n=p_1^{\alpha 1}\cdot p_2^{\alpha 2}\cdot \cdot \cdot p_k^{\alpha k}$ ，只需要关注质因数的种类，又因为$1\le a_i\le 5\times 10^5$ ，$2\ast 3\ast 5\ast 7\ast 11\ast 13\ast 17=510510>10^5$，故 $p$ 的种类最多有六个，那也就是最多有 $2^6$ 种组合，时间复杂度 $O(q\ast 2^6)$

code

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int, int>

using namespace std;
const int N = 5e5 + 1000;
int prime[N], sum[N], cnt = 0;
bool st[N], vis[N];
vector<int> p[N];
int ans = 0;

void is_prime(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i])
            prime[cnt++] = i;
        for (int j = 0; j < cnt && i * prime[j] <= n; ++j)
        {
            st[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}

void query(int x, int op)
{
    for (int i = 0; i < (1ll << p[x].size()); ++i)
    {
        int now = 1, num = 0;
        for (int j = 0; j < p[x].size(); ++j)
            if ((1ll << j) & i)
                now *= p[x][j], num++;
        if (num & 1)
            ans -= op * sum[now];
        else
            ans += op * sum[now];
    }
}

void updata(int x, int op)
{
    for (int i = 0; i < (1ll << p[x].size()); ++i)
    {
        int now = 1;
        for (int j = 0; j < p[x].size(); ++j)
            if ((1ll << j) & i)
                now *= p[x][j];
        sum[now] += op;
    }
}
void solve()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        for (int j = 0; j < cnt && prime[j] <= sqrt(x); ++j)
        {
            if (x % prime[j] == 0)
            {
                p[i].push_back(prime[j]);
                while (x % prime[j] == 0)
                    x /= prime[j];
            }
        }
        if (x > 1)
            p[i].push_back(x);
    }
    while (q--)
    {
        int x;
        cin >> x;
        if (!vis[x])
            query(x, 1), updata(x, 1);
        else
            updata(x, -1), query(x, -1);
        cout << ans << '\n';
        vis[x] ^= 1;
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    is_prime(5e5 + 10);
    int t = 1;
    while (t--)
        solve();
    return 0;
}