[백준 C++] 11689 GCD(n, k) = 1 - 오일러피

11689번: GCD(n, k) = 1

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	long long N;
	cin >> N;

	long long P = N;
	for (int i = 2; i <= sqrt(N); ++i)
	{
		if (N % i != 0)
		{
			continue;
		}

		P = P - P / i;
		while (N % i == 0)
		{
			N /= i;
		}
	}

	if (N > 1)
	{
		P = P - P / N;
	}

	cout << P;
}

---

 

1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 출력하는 문제입니다.

오일러 피 함수(P[N] = P[N] - P[N] / K)를 이용하고, 탐색 범위를 소인수 분해를 통해서 좁혀나가도록 해서 풀었습니다.

N의 입력 가능 범위가 크기 때문에 자료형과 시간 복잡도 측면에서 주의가 필요합니다.