백준9359 서로소

작성일 | In

문제 링크

  • http://icpc.me/9359

문제 출처

  • 2011 LCPC B번

사용 알고리즘

  • BitMask

풀이

처음에는 오일러 파이 함수를 생각해봤으나, 구현이 귀찮아서 다른 방법을 이용했습니다.

n을 소인수 분해를 하기 위해서는 n 이하의 소수를 구해야 합니다. 에라토스테네스의 체를 이용하면 O(n lg lg n)에 구할 수 있지만, n이 최대 10억입니다.
그러나 n의 가장 큰 소인수는 몰라도 두 번째로 큰 소인수부터는 항상 sqrt(n)보다 작습니다. 그러므로 10만 정도까지만 구해도 괜찮습니다.

n이 최대 10억이라는 것은, 소인수가 최대 9개 밖에 없다는 것을 의미합니다. 그러므로 2^9번의 계산을 통해 포함-배제를 사용하면 빠르게 답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vi;

vi prime;
vi divi;
map<ll, int> m;

void eratos(int n){
	vi chk(n+1, 1);
	for(int i=2; i<=n; i++){
		if(chk[i]){
			prime.push_back(i);
			for(int j=i+i; j<=n; j+=i) chk[j] = 0;
		}
	}
}

void f(int idx){
	ll a, b, n; scanf("%lld %lld %lld", &a, &b, &n);
	divi.clear();
	m.clear();
	bool flag = 1;
	while(n > 1){
		flag = 1;
		for(auto i : prime){
			if(n%i == 0){
				n /= i;
				flag = 0;
				m[i] = 1;
				break;
			}
		}
		if(flag) break;
	}
	if(n != 1) m[n] = 1;
	for(auto i : m){
		divi.push_back(i.first);
	}

	ll ans = 0;
	ll bit = 1 << divi.size();
	for(int i=1; i<bit; i++){
		ll cnt = 0, sum = 1;
		for(int j=0; j<divi.size(); j++){
			if( !(i & (1 << j)) ) continue;
			cnt++; sum *= divi[j];
		}
		ll aa = (a+sum-1)/sum;
		ll bb = (b)/sum;
		if(aa > bb) continue;
		if(cnt&1) ans += bb-aa+1;
		else ans -= bb-aa+1;
	}
	printf("Case #%d: %lld\n", idx, b-a+1-ans);
}

int main(){

	eratos(100000);
	int t; cin >> t; for(int i=1; i<=t; i++) f(i);
}