백준 23832번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	512MB	골드 1

---

풀이

 밀린 문제 정리하기. 이번에도 여전히 오일러 피함수이다.

 

 이 문제는 1~N번 정점을 그래프로 만들 것이다. 이때 정점간에 간선을 만드는 조건은 정점 a, b가 각각 서로소여야 한다. 이때 간선의 개수를 구하는 문제이다. 나는 처음에 이게 오일러 피함수 문제인지 헷갈렸다. 서로소의 개수와 연관되이었다보니 오일러 피함수가 가능할 것 같다 생객해보다가 풀이를 떠올렸다. 문제가 조금 말이 어려워서 그렇지 조금 차근차근 풀어나가보자.

 

간선 없이 정점만 놓고 생각해보자. 임의의 정점 a는 a보다 큰 서로소인 정수와도 연결되어야 하고, a보다 작은 서로소와도 연결되어야 한다. a보다 작은 서로소는 세기 쉬운데, a보다 큰 서로소 정수는 찾기가 애매하다. 생각을 바꿔보면, a보다 큰 서로소 정수는 a보다 더 큰 정점 b에서 b보다 작은 서로소를 향해 간선을 만들었을 것이다. 따라서, 모든 정점을 순회하며 해당 정점번호보다 작은 서로소 정수의 개수를 세면 된다. 주의해야할 점은 오일러 피함수의 1의 결과값은 1이지만, 여기서는 본인보다 작은 개수를 세야하기 때문에 해당 문제에서는 0으로 처리해야한다.

 

코드

#include <bits/stdc++.h>
using namespace std;
using ul = uint64_t;

int n;

ul euler_phi(int n) {
	if (n == 1) return (ul)0;
	ul res = n;
	for (ul i = 2; i * i <= n; i++) {
		if (n % i) continue;
		res /= i;
		res *= (i - 1);
		while (n % i == 0) n /= i;
	}
	if (n != 1) {
		res /= n;
		res *= (n - 1);
	}

	return res;
}

void sol() {
	ul res = 0;
	for (int i = 1; i <= n; i++) {
		res += euler_phi(i);
	}
	cout << res;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n;
	sol();
}