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];elseans += 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);elseupdata(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;
}