[BOJ 1750 // C++] 서로소의 개수

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

 

이번에 볼 문제는 백준 1750번 문제인 서로소의 개수이다.
문제는 아래 링크를 확인하자.

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

1750번: 서로소의 개수

주어진 길이 $N$의 수열의 원소를 선택하는 경우의 수는 각 원소를 선택하거나 안하거나의 관점에서 보았을 때 $2^N-1$과 같음을 관찰하자. -1은 아무 원소도 고르지 않는 경우를 제외한 것이다.

 

선택한 원소가 서로소이게 원소를 고르는 경우의 수는 전체 경우의 수에서 선택한 원소가 서로소가 아니게 원소를 고르는 경우의 수를 빼는 것으로 구할 수 있다. 그 경우의 수는 10만 이하의 양의 정수 k에 대하여 주어진 원소들이 모두 k의 배수가 되도록 원소를 고르는 경우의 수를 구할 수 있다면 포제원리(inclusion and exclusion principle)와 뫼비우스 함수(möbius function)를 이용해 빠르게 계산해낼 수 있다. 전체 원소의 개수가 50, 즉 충분히 적은 수이므로 위에서 필요한 값은 주어진 원소 중 k의 배수의 개수를 직접 세는 것으로 충분히 빠르게 구할 수 있다.

 

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

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

char mobius[100001];
bool sieve[100001];

int N;
int arr[50];
ll ans;

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

	for (int i = 1; i < 100001; i++) mobius[i] = 1;
	for (int i = 2; i < 100001; i++) {
		if (sieve[i]) continue;
		for (int j = i; j < 100001; j += i) {
			mobius[j] *= -1;
			sieve[j] = 1;
		}
		ll sq = (ll)i * i;
		for (ll j = sq; j < 100001; j += sq) mobius[j] = 0;
	}

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	ans = (1LL << N) - 1;
	for (int i = 2; i < 100001; i++) {
		int cnt = 0;
		for (int j = 0; j < N; j++) {
			if (arr[j] % i) continue;
			cnt++;
		}

		ans += ((1LL << cnt) - 1) * mobius[i];
	}

	cout << ans % 10000003;
}