백준11689 GCD(n, k) = 1

작성일 | In

문제 링크

  • http://icpc.me/11689

풀이

N의 소인수를 모두 구한 뒤, 포함배제를 잘 사용하면 됩니다.

N은 최대 10^12입니다. 1부터 sqrt(N)까지의 소수만 구해놓는다면, N의 소인수를 구할 수 있습니다.
N의 가장 큰 소인수가 sqrt(N)보다 작다면, 모든 소인수는 sqrt(N)보다 작습니다.
만약 가장 큰 소인수가 sqrt(N)보다 크더라도, 두 번째로 큰 소인수는 sqrt(N)보다 작다는 사실을 알 수 있습니다.

그러므로 10^6정도까지의 소수를 에라토스테네스의 체를 이용해 구해줍시다.
소인수를 구하는 코드는 아래처럼 작성할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
set<int> s;
while(1){
  bool flag = 1;
  for(auto i : prime){
    if(n % i == 0){
      flag = 0; s.insert(i);
      n /= i;
    }
  }
  if(flag) break;
}
if(n != 1){
  s.insert(n);
}

10^12 이하의 수는 소인수가 아무리 많아도 11개를 넘지 않습니다. 그러므로 비트마스크를 이용해 포함배제를 해주면 소인수의 개수를 찾을 수 있습니다.
자세한 구현은 코드를 봐주세요.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll> prime;
int chk[1010101];
set<ll> s;
vector<ll> fac;

void f(){
	for(int i=2; i<=1000000; i++){
		if(chk[i]) continue;
		prime.push_back(i);
		for(int j=i+i; j<=1000000; j+=i) chk[j] = 1;
	}
}

int main(){
	f();
	ll n; cin >> n;
	ll t = n;
	while(1){
		bool flag = 1;
		for(auto i : prime){
			if(n % i == 0){
				flag = 0; s.insert(i);
				n /= i;
			}
		}
		if(flag) break;
	}
	if(n != 1){
		s.insert(n);
	}
	for(auto i : s) fac.push_back(i);

	ll ans = 0;
	int m = fac.size();
	for(int bit=1; bit<(1<<m); bit++){
		ll now = 1, cnt = 0;
		for(int j=0; j<m; j++) if(bit & (1<<j)) now *= fac[j], cnt++;
		if(cnt & 1) ans += (t/now);
		else ans -= (t/now);
	}
	cout << (t - ans);
}