题目链接：点击打开链接
题意：
给定n个数，q个操作
下面n个数 a1-an
开始有一个空的集合
每个操作一个数字 u (1<=u<=n) 表示把 a[u] 插入集合（若集合中没有a[u]), 否则就把a[u]从集合中删除
每个操作结束后输出 当前集合内有多少对数 是互质的。
思路：
分解质因素，然后容斥一下求 与a[u] 不互质的个数，做个差即可。
PS: 在微软（苏州）bop现场和kuangbin，19891101 ，Jayye, xiaoxin等晚上一起在宾馆打的cf~
#include <iostream>#include <fstream>#include <string>#include <time.h>#include <vector>#include <map>#include <queue>#include <algorithm>#include <cstring>#include <cmath>#include <set>#include <vector>using namespace std;template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if (x>9) pt(x / 10);putchar(x % 10 + '0');}typedef long long ll;const int N = 5e5 + 10;int prime[N], primenum;//有primenum个素数 math.h void PRIME(ll Max_Prime){primenum = 0;prime[primenum++] = 2;for (ll i = 3; i <= Max_Prime; i += 2)for (ll j = 0; j<primenum; j++)if (i%prime[j] == 0)break;else if (prime[j]>sqrt((double)i) || j == primenum – 1){prime[primenum++] = i;break;}}int n, q;int a[N];vector<int>G[N];ll ans;void pre(int u, int x){for (int i = 0; prime[i] * prime[i] <= x; i++){if (x%prime[i] == 0){while (x%prime[i] == 0)x /= prime[i];G[u].push_back(prime[i]);}}if (x != 1)G[u].push_back(x);}set<int>s;int f[N];int c[N], top;void dfs(int t, int x, int cnt, int flag, int val){if (t >= (int) G[x].size()){if (cnt == 0)return;ans += f[val] * flag;c[top++] = val;return;}dfs(t + 1, x, cnt, flag, val);dfs(t + 1, x, cnt + 1, flag*-1, val*G[x][t]);}void p(){printf(" set:"); for (auto it : s){printf("%d ", it);}puts("");}int one;int main(){PRIME(N);rd(n); rd(q);for (int i = 1; i <= n; i++) {rd(a[i]);pre(i, a[i]);}ans = 0;one = 0;while (q–){int u; rd(u);if (a[u] == 1){if (s.count(u)){one–;s.erase(u);ans -= s.size();}else {ans += s.size();one++;s.insert(u);}}else{//printf("ans:%d, one:%d "); p();if (s.count(u)){s.erase(u);ans -= s.size();top = 0;dfs(0, u, 0, -1, 1);ans–; //删掉自己与自己的组合for (int i = 0; i < top; i++)f[c[i]] –;}else {ans += s.size();s.insert(u);top = 0;dfs(0, u, 0, 1, 1);for (int i = 0; i < top; i++)f[c[i]] ++;}}cout << " "; pt(ans); puts("");}return 0;}
，最有效的资本是我们的信誉，它24小时不停为我们工作。
