취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 8291번 문제인 Coprime Numbers이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/8291 

1의 배수의 쌍의 개수, 2의 배수의 쌍의 개수, ..., 300만의 배수의 쌍의 개수는 각각의 \(k\)에 대하여 주어진 수열의 \(k\)의 배수의 개수를 안다면 구해낼 수 있다. 모든 \(N\) 이하의 \(k\)에 대하여 주어진 수열의 \(k\)의 배수의 개수를 구하는 것은 주어질 수 있는 수의 최댓값을 \(M\)이라 할 때 에라토스테네스의 체와 같은 원리로 \(O(MlgM)\)에 해낼 수 있다.

문제의 답은 포제원리(inclusion and exclusion)에 의해 1의 배수의 쌍의 개수 - (서로 다른 소수 1개의 곱의 배수들의 각각 이룰 수 있는 쌍의 개수) + (서로 다른 소수 2개의 곱의 배수들의 각각 이룰 수 있는 쌍의 개수) - (서로 다른 소수 3개의 곱의 배수들의 각각 이룰 수 있는 쌍의 개수) +... 와 같이 구할 수 있음을 관찰하자. 각 수에 대하여 위의 부호를 결정짓는 데 사용할 뫼비우스 함수의 값들을 먼저 구한 다음 위의 식을 계산하는 것으로 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N;
int arrcnt[3000001];
int cnt[3000001];
char mobius[3000001];
bool sieve[3000001];

ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	cnt[1] = N;
	while (N--) {
		int x; cin >> x;
		arrcnt[x]++;
	}
	
	for (int i = 1; i < 3000001; i++) mobius[i] = 1;
	for (int i = 2; i < 3000001; i++) {
		if (sieve[i]) {
			for (int j = i; j < 3000001; j += i) cnt[i] += arrcnt[j];
		}
		else {
			for (int j = i; j < 3000001; j += i) mobius[j] *= -1, cnt[i] += arrcnt[j], sieve[j] = 1;
			ll sq = (ll)i * i;
			for (ll j = sq; j < 3000001; j += sq) mobius[j] = 0;
		}
	}

	for (int i = 1; i < 3000001; i++) {
		ans += (ll)mobius[i] * cnt[i] * (cnt[i] - 1) / 2;
	}

	cout << ans;
}