http://codeforces.com/problemset/problem/548/E
这题是询问id，如果这个id不在，就插入这个id，然后求a[id1] , a[id2]互质的对数。
询问有多少个互质这个套路出了很多次，这次是在线
首先维护当前的ans，可以知道每一步的ans，都是由于上一步的ans递推过来的。就是小答案可以由大答案推过来。
就是现在数组是a[] = 1, 2, 3，维护一个ans表示有多少对gcd等于1，然后添加一个4，只需要询问4在a[] = {1, 2, 3}中有多少个和它互质，即可。
（有时候也需要总体分析。- - ，与这题无关）
分析：
怎么说呢，很久之后我看到这题，发现压根就没写详解，虽然自己记得具体解法，但是却没理论论证。想了一晚，现在回忆起来了。
难点就是在于给定一个集合，然后给你一个数，问这个集合里面有多少个数与它互质。
比如现在集合是：4、6、8、9、11
询问数字：12
与它gcd = 1， 相当于 size - (gcd != 1)对立面。
设gcd[i]表示与查询数gcd = i的总数
然后就是相当于 size - (gcd[2] + gcd[3] + gcd[4] + gcd[5] + ..... + gcd[12])
然后这样很明显会是减多了。比如gcd[6]，会在gcd[2]的时候减一次，gcd[3]减一次，gcd[6]减一次。这样相当于减了3次。
所以每个gcd[i]前面应该还有一个系数控制它减多少。这个系数嘛，就是mobius[i]，这个就不说啦，当我们都懂了。就是gcd的容斥。
比如mobius[4] = 0，因为gcd[4]会在gcd[2]和gcd[4]的时候各减去一次，同时需要保留一次，就保留了gcd = 2的，(mobius[2] = -1)
而mobius[6] = 1，因为gcd[6]，会在gcd[2]的时候减一次，gcd[3]减一次，gcd[6]减一次。这样相当于减了3次。那么如果在gcd[6]的时候加回一次，就相当于减去了一次而已。满足条件。
回到题目，如果每次都和上面这样做，复杂度O（val），因为要枚举2----val之间的数字。
但是有很多东西是不必要的枚举，比如枚举gcd[7]，根本没有数字可能与12 gcd = 7
所以只需要枚举12的因子即可，12 = 2 * 2 * 3，因子有2、3、4、6、12，每个因子是加是减，也是由Mobius[i]决定。
但是这样枚举也很多的哦，
首先知道没必要枚举4，因为mobius[4] = 0，也没必要枚举12，同理mobius[12] = 0
那么把12写成 12 = 2 * 3，就是每个质因子出现的次数只保留一次，然后有约数是2、3、6，去容斥即可，奇加偶减
做到了每个数字的mobius[i]都 != 0，枚举都是有必要的。
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = + ;
int prime[maxn][], a[maxn];
void init() {
for (int i = ; i <= maxn - ; ++i) {
if (prime[i][]) continue;
for (int j = i; j <= maxn - ; j += i) {
prime[j][++prime[j][]] = i;
}
}
// prime[1][0] = 1;
// prime[1][1] = 1;
}
bool in[maxn];
int num[maxn];
void maintain(int val, int op) {
int en = ( << prime[val][]) - ;
for (int i = ; i <= en; ++i) {
int res = ;
for (int j = ; j <= prime[val][]; ++j) {
if (i & ( << (j - ))) res *= prime[val][j];
}
num[res] += op;
}
}
LL ans;
LL getAns(int val) {
LL ans = ;
int en = ( << prime[val][]) - ;
for (int i = ; i <= en; ++i) {
int res = ;
int sel = ;
for (int j = ; j <= prime[val][]; ++j) {
if (i & ( << (j - ))) {
++sel;
res *= prime[val][j];
}
}
if (sel & ) ans += num[res];
else ans -= num[res];
}
return ans;
}
void work() {
int n, q, tot = ;
scanf("%d%d", &n, &q);
for (int i = ; i <= n; ++i) scanf("%d", a + i);
for (int i = ; i <= q; ++i) {
int id;
scanf("%d", &id);
if (in[id]) {
maintain(a[id], -);
in[id] = false;
ans -= getAns(a[id]);
tot--;
} else {
ans += getAns(a[id]);
maintain(a[id], );
in[id] = true;
tot++;
}
printf("%I64d\n", 1LL * tot * (tot - ) / - ans);
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
init();
// int val = 4;
// for (int i = 1; i <= prime[val][0]; ++i) {
// printf("%d ", prime[val][i]);
// }
// printf("\n");
work();
return ;
}