BOJ 9359 - 서로소 (포함배제)

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

포함배제에 대한 자세한 설명: https://zzonglove.tistory.com/35

 

<문제설명>

a,b,n이 주어진다. a,b사이의 수 중 n과 서로소인 수의 개수를 구하여라. (n<=1e9)

 

<풀이>

n<=1e9인 경우 소인수는 많아봤자 9개이다. (2부터 29까지 소수들 10개 곱하면 6e9를 넘어감)

 

a,b사이의 수 중 n과 서로소가 아닌 수의 개수를 세서 전체에서 빼주면 된다.

 

a,b사이의 수 중 n과 서로소가 아닌 수는, n의 소인수들 중 하나 이상의 배수이면 된다.

->a,b사이의 수 중 n의 소인수의 배수의 개수를 세주면 된다. (합집합)

 

<코드>

ll gcd(ll a, ll b) {
	if (a < b) swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}

int main() {
	FAST;
	int tt; cin >> tt;
	for (int tc = 1; tc <= tt; tc++) {
		ll a, b, n;
		cin >> a >> b >> n;
		ll ans = b - a + 1;

		//n <= 1e9, 소인수개수 최대 10개정도
		ll temp = n;
		vector<ll> comp; //n의 소인수
		for (ll i = 2; i * i <= n; i++) {
			if (temp % i == 0) {
				comp.push_back(i);
				while (temp % i == 0) temp /= i;
			}
		}
		if (temp != 1) comp.push_back(temp);

		ll k = comp.size(), sum = 0;
		for (ll i = 1; i < (1ll << k); i++) {
			ll cnt = 0, lcm = 0;
			for (ll j = 0; j < k; j++) {
				if (i & (1 << j)) {
					cnt++;
					if (lcm == 0) lcm = comp[j];
					else lcm = lcm * comp[j] / gcd(lcm, comp[j]);
				}
			}
			if (cnt > 0) {	//공집합을 고려하지 않으므로 이 껍질 벗겨도 된다.
				ll d = b / lcm - (a - 1) / lcm;
				if (cnt % 2 == 1) sum += d;
				else if (cnt > 0) sum -= d;
			}
		}

		cout << "Case #" << tc << ": " << ans - sum << '\n';
	}
}