백준 11689번 C++ 풀이

문제

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

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

---

풀이

 밀린 문제 정리하기, 오일러 피함수 문제는 계속된다. 오일러 피함수에 대해 계속 정리중이기 때문에, 해당 문제는 오일러 피함수 문제임을 바로 알 수 있다. 말이 수식으로 나와서 어려울수 있지만, 자연수 n에 대해 n 이하의 자연수 k가 GCD(n, k) = 1을 만족한다는 뜻은 n과 k는 서로소라는 뜻과 동치이다. 오일러 피함수는 n 이하의 n과 서로소인 자연수의 개수를 세는 함수이기 때문에 오일러 피함수를 사용하는 문제임을 알 수 있다.

코드

#include <iostream>
using namespace std;
using ul = uint64_t;

ul n;

void sol() {
	ul res = n;

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

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