Codeforces 548E（莫反、容斥）

转化为质数域上的操作，如果用莫反的话，记录因数的cnt。

其实莫反的推式子最后和容斥做法殊途同归了，容斥的系数就是莫比乌斯函数。

const int maxn = 2e5 + 5, maxa = 5e5 + 5;

int n, q, a[maxn], maxx;

int primes[maxa], tot, vis[maxa], mu[maxa];

vector<int> fac[maxa];

ll ans;

int g[maxa];

bool mark[maxn];

void Pre() {

	mu[1] = 1;

	for (int i = 2; i <= maxx; i++) {

		if (!vis[i]) {

			primes[++tot] = i;

			mu[i] = -1;

		}

		for (int j = 1; j <= tot && (ll)primes[j] * i <= maxx; j++) {

			vis[primes[j] * i] = 1;

			if (i % primes[j] == 0)	break;

			mu[primes[j] * i] = -mu[i];

		}

	}5

	for (int i = 1; i <= maxx; i++)

		for (int j = 1; (ll)j * i <= maxx; j++)

			fac[j * i].push_back(i);

}

int main() {

	read(n), read(q);

	rep(i, 1, n)	read(a[i]), maxx = max(maxx, a[i]);

	Pre();

	for (int i; q; q--) {

		read(i);

		if (!mark[i]) {

			mark[i] = 1;

			for (int d : fac[a[i]]) {

				ans += mu[d] * g[d];

				g[d]++;

			}

		} else {

			mark[i] = 0;

			for (int d : fac[a[i]]) {

				g[d]--;

				ans -= mu[d] * g[d];

			}

		}

		writeln(ans);

	}

	return 0;

}

巴特西

Codeforces 548E（莫反、容斥）

最新文章

热门文章