[백준] GCD(n, k) = 1 c++

GCD(n, k) = 1 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

14110

5582

4443

39.948%

문제

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다.

출력

GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.

---

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
	long N;
	cin >> N;

	long result = N;

	//소인수 분해 방식
	for (long i = 2; i <= sqrt(N); i++)
	{
		if (N % i == 0)
		{
			//오일러 피 함수 공식을 적용
			result -= result / i;

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

	//N이 소수가 아니라면 업데이트
	if (N > 1)
	{
		result -= result / N;
	}

	cout << result;
}

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