Codeforces Round #305 Div2 E: Mike and Foam（素因数分解・包除原理）

問題

codeforces.com

解法

mayokoex.hatenablog.com

例えば、棚に(1, 2, 3, 4, 6)が入っていて、6を入れる場合を考える。

1. 1, 2, 3, 4, 6と6は公約数として1をもつので、とりあえず回答を5とする。
2. このうち、2, 4, 6の3つは6と公約数として2をもつので除外して、回答を5-3=2とする。
3. また、3, 6の2つは6と公約数として3をもつので除外して、回答を2-2=0とする。
4. 6と6は公約数として2*3をもつので、2の時と3の時で重複して除外しているから、戻して、回答を0+1=1とする。
5. 実際に1, 2, 3, 4, 6のある棚に6を入れると新たに出来るペアは(1, 6)の1つだけなので正しい答えが導き出せている。

棚に新しくa=p1*p2*p3*...を入れる時、いま棚にある数字のうち公約数として1をもつものの数（要するに全部）を足して、公約数としてp1をもつもの、p2をもつもの、...の数を引いて、公約数としてp1*p2をもつもの、p1*p3をもつもの、...p2*p3をもつもの...の数を足して、...という事を交互に繰り返すことで、互いに素なものとのペアだけを求めることが出来る。

コード

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	private final int MAX = 500002;

	public void solve() {
		Scanner sc = new Scanner(System.in);
		// divisor[i]:= iの約数となる最小の素数
		int[] divisor = new int[MAX];
		for (int i = 1; i < MAX; i++) {
			divisor[i] = i;
		}
		for (int i = 2; i < MAX; i++) {
			if (divisor[i] == i) {
				for (int j = i * 2; j < MAX; j += i) {
					divisor[j] = Math.min(divisor[j], i);
				}
			}
		}

		int N = sc.nextInt();
		int Q = sc.nextInt();
		int[] a = new int[N];
		for (int i = 0; i < N; i++) {
			a[i] = sc.nextInt();
		}

		// innerCount[p]:= 棚に入っているものの中でpを約数にもつものの数
		int[] innerCount = new int[MAX];

		boolean[] isIn = new boolean[N];

		long answer = 0;
		StringBuilder sb = new StringBuilder();
		for (int q = 0; q < Q; q++) {
			int id = sc.nextInt() - 1;
			ArrayList<Integer> primes = new ArrayList<>();
			int volume = a[id];
			while (volume != 1) {
				int p = divisor[volume];
				primes.add(p);
				while (volume % p == 0) {
					volume /= p;
				}
			}

			int primeSize = primes.size();
			for (int bit = 0; bit < (1 << primeSize); bit++) {
				int cur = 1;
				for (int i = 0; i < primeSize; i++) {
					if ((bit & (1 << i)) != 0) {
						cur *= primes.get(i);
					}
				}

				if (!isIn[id]) {
					if (Integer.bitCount(bit) % 2 == 0) {
						answer += innerCount[cur];
					} else {
						answer -= innerCount[cur];
					}
					innerCount[cur]++;
				} else {
					innerCount[cur]--;
					if (Integer.bitCount(bit) % 2 == 0) {
						answer -= innerCount[cur];
					} else {
						answer += innerCount[cur];
					}
				}
			}
			isIn[id] = !isIn[id];
			sb.append(answer);
			sb.append("\n");
		}
		sc.close();
		System.out.println(sb.toString());
	}

	public static void main(String[] args) {
		new Main().solve();
	}

}