[백준] 11689번 : GCD(n, k) = 1 C++ 문제풀이 솔루션

 

문제

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

입력

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

출력

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

 

 

GCD(n, k) = 1을 만족하는 자연수의 개수가 오일러 피 함수의 정의입니다.

오일러 피 함수를 구현하여 문제를 해결할 수 있습니다.

 

구하고자 하는 범위까지 배열을 생성하고 2부터 배수마다 p[i] = p[i] - p[i]/k 연산을 수행하고 연산을 수행한 수를 모두 나누어 이 수와 서로소를 만듭니다.

이를 범위의 최대값의 제곱근까지 진행하면 됩니다.

 

이 과정 후 최대값이 1보다 크다면 연산을 한 번 더 진행하여 소수를 나누어 없앱니다.

#include <iostream>
#include <algorithm>
#include <cmath>

#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false)
#define ll long long

using namespace std;
int main() {
  fast_io;
  ll n;
  cin >> n;
  ll disjoint = n; //서로소 개수
  for (ll i = 2; i <= sqrt(n); i++) { //오일러 피 함수
	if (n % i == 0) disjoint = (disjoint - disjoint / i);
	while (n % i == 0) n /= i;
  }
  if (n > 1) disjoint = disjoint - disjoint / n;
  cout << disjoint;
  return 0;
}