취미로 코딩하기

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

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

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

A 이상 B 이하의 자연수 중 N과 서로소인 수의 개수를 구하는 문제이다.

다르게 쓰면, (B 이하의 자연수 중 N과 서로소인 수) - (A-1 이하의 자연수 중 N과 서로소인 수)를 구하는 문제이다.

따라서, X 이하의 자연수 중 N과 서로소인 수를 구하는 방법을 찾으면 문제를 해결할 수 있다.

포제원리(inclusion-exclusion principle)를 이용하여 X 이하의 자연수를 찾자.

구현은 N의 소인수들을 구해 이 소인수들의 곱의 경우의 수들을 이용하는 것으로 할 수 있다.

가장 작은 10개의 소수들을 모두 곱해도 10억은 넘기므로 살펴봐야 하는 경우의 수는 많지 않다는 것을 알 수 있고, 따라서 비트마스크를 이용하여 포제원리를 구현하면 문제를 해결할 수 있다.

여담으로 글쓴이는 A-1을 제대로 처리하지 않아 몇번 틀렸다(...).

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

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

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

	int T; cin >> T;
	for (int t = 1; t <= T; t++) {
		ll A, B, N; cin >> A >> B >> N; A--;
		ll ansA = A, ansB = B;
		vector<ll> primes;
		
		for (ll p = 2; p * p <= N; p++) {
			if (N % p == 0) {
				primes.emplace_back(p);
				while (N % p == 0) N /= p;
			}
		}

		if (N > 1) primes.emplace_back(N);

		int R = 1 << primes.size();
		for (int i = 1; i < R; i++) {
			int sgn = 0;
			int idx = 0, ii = i;
			ll div = 1;
			while (ii) {
				if (ii & 1) {
					div *= primes[idx];
					sgn ^= 1;
				}
				ii >>= 1;
				idx++;
			}
			if (sgn) {
				ansA -= A / div, ansB -= B / div;
			}
			else {
				ansA += A / div, ansB += B / div;
			}
		}

		cout << "Case #" << t << ": " << ansB - ansA << '\n';
	}
}