C++(g++ 7.5.0) 解法, 执行用时: 993ms, 内存消耗: 12576K, 提交时间: 2022-10-02 17:41:54

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0), 1
using namespace std;

const int N = 5e5 + 10;

typedef long long LL;

int n, q, k;
int cnt, p[N], moi[N], a[N];
bool st[N], vis[N];
LL ans, f[N];

void init()
{
	moi[1] = 1;
	for(int i = 2; i <= N; i ++)
	{
		if(!st[i]) p[cnt ++] = i, moi[i] = -1;

		for(int j = 0; i * p[j] <= N; j ++)	
		{
			st[i * p[j]] = 1;
			if(i % p[j] == 0) break;
			moi[i * p[j]] = -moi[i];
		}	
	}	
}

void sovle(bool x, int id)
{
	int n = a[id];
	for(int i = 1; i * i <= n; i ++)
	{
		if(n % i) continue;
		
		ans -= (f[i] - 1) * f[i] / 2 * moi[i];
		f[i] += (x) ? 1 : -1;
		ans += (f[i] - 1) * f[i] / 2 * moi[i];
		
		if(i * i == n) return ;
		 
		int j = n / i;
		ans -= (f[j] - 1) * f[j] / 2 * moi[j];
		f[j] += (x) ? 1 : -1;
		ans += (f[j] - 1) * f[j] / 2 * moi[j];
	}	
}

int main()
{
	IOS;
	init();

	cin >> n >> q;
	for(int i = 1; i <= n; i ++)
		cin >> a[i];
		
	while(q --)
	{
		cin >> k;
		vis[k] ^= 1;
		sovle(vis[k], k);
		cout << ans << endl;
	}
	
	return 0;
}

C++ 解法, 执行用时: 526ms, 内存消耗: 5960K, 提交时间: 2022-03-05 16:56:57

#include <bits/stdc++.h>
using namespace std;
#define N 100005
 
int a[2 * N], n, b[5 * N], vis[2 * N], q[N], qs;
long long ans;
 
void func(int v, int x, int y, int d) {
	if (x == qs) {
		if(v) {
			b[y] --;
			if (d) ans += b[y];
			else ans -= b[y];
		}
		else {
			if (d) ans -= b[y];
			else ans += b[y];
			b[y] ++;
		}
	}
	else {
		func(v, x + 1, y, d);
		func(v, x + 1, y * q[x], 1 - d);
	}
}
 
int main() {
	int i, k, m, d, qr;
	scanf("%d %d", &n, &qr);
	for (i = 1; i <= n; i ++) scanf("%d", a + i);
	while (qr --) {
		scanf("%d", &k);
		d = a[k]; m = sqrt(d); qs = 0;
		for (i = 2; i <= m; i ++) {
			if (d % i == 0) q[qs ++] = i;
			while (d % i == 0) d /= i;
		}
		if (d > 1) q[qs ++] = d;
		func(vis[k], 0, 1, 0);
		vis[k] ^= 1;
		printf("%lld\n", ans);
	}
}