题目

有 $n$ 个正整数 $a_n$。现在有一个下标集合 $S$，初始时为空，你需要依次实现 $q$ 次操作：

每次操作会给定一个整数 $x(1\leq x\leq n)$，如果当前 $x$ 不在下标集合 $S$ 中，则在 $S$ 中加入 $x$，否则删去 $x$。 每次操作过后，你都需要计算下面这个式子的值：

$$\sum_{i<j,i,j\in S}[\gcd(a_i,a_j)=1]$$

分析

见到这样的式子，用莫比乌斯反演：

$$\begin{aligned}\sum_{i<j,i,j\in S}[\gcd(a_i,a_j)=1]&=\sum_{i<j,i,j\in S}\sum_{k|\gcd(a_i,a_j)}\mu(k)\\ &=\sum_k\mu(k)\sum_{k|a_i}\sum_{k|a_j}1\end{aligned}$$

那么每次对 $x$ 进行一个操作，只用枚举 $x$ 的所有因数 $k$（相当于枚举最大公约数），看看有多少个 $k$ 的倍数。时间复杂度 $\mathcal{O}(q\sqrt{n})$

代码

const int N = 1e5 + 10, M = 5e5 + 10;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int n, t;
int a[N];

int pri[M], cnt, mu[M];
bool vis[M];
void Init() {
	mu[1] = 1;
	for (int i = 2; i <= M - 10; i++) {
		if (!vis[i]) pri[++cnt] = i, mu[i] = -1;
		for (int j = 1; j <= cnt && i * pri[j] <= M - 10; j++) {
			vis[i * pri[j]] = 1;
			mu[i * pri[j]] = -mu[i];
			if (i % pri[j] == 0) {
				mu[i * pri[j]] = 0;
				break;
			}
		}
	}
}

int cunt[M];
bool been[N];
ll ans;

int main() {
	freopen("pair.in", "r", stdin);
	freopen("pair.out", "w", stdout);
	Init();
	n = Read(), t = Read();
	for (int i = 1; i <= n; i++) a[i] = Read();
	for (; t--; ) {
		int now = Read();
		ll sum = 0;
		for (int i = 1; i * i <= a[now]; i++) {
			if (a[now] % i) continue;
			sum += mu[i] * cunt[i];
			cunt[i] += been[now]? -1: 1;
			if (i * i != a[now]) {
				sum += mu[a[now] / i] * cunt[a[now] / i];
				cunt[a[now] / i] += been[now]? -1: 1;
			}
		}
		if (been[now]) ans -= sum - (a[now] == 1);
		else ans += sum;
		been[now] ^= 1;
		printf ("%lld\n", ans);
	}
	return 0;
}