백준11689_GCD(n, k) = 1

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

 

 

문제

자연수 n이 주어졌을 때, 1~n 의 자연수 중 n 과 서로소인 숫자의 개수를 구하는 문제이다.

 

접근 방법

오일러 파이 함수를 이용해야 한다.

이는 1부터 n까지의 수 중에서 n과 서로소인 수의 개수를 계산하는 함수이므로 이 문제를 해결하기에 적합하다.

따라서, n의 소인수만 찾으면 효율적으로 계산이 가능하다.

 

오일러 피 함수의 원리는 에라토스테네스의 체와 비슷하다.

이렇게, 소수를 찾아서 순차적으로 p[i] = p[i] - (p[i]/2) 연산을 반복적으로 수행해주면 최종 결과는 오일러 피 함수의 결괏값이 배열에 남게 된다.

 

코드

#include <cmath>
#include <iostream>
#include <string>
#include <vector>

// 오일러 파이 함수 구현
long long euler_totient(long long n) {
  long long result = n; // 초기값은 n

  // 소인수 찾기
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) { // 소인수 발견
      while (n % i == 0) { // n에서 i의 배수를 제거
        n /= i;
      }
      result -= result / i; // 결과 갱신
    }
  }

  // 마지막 남은 소수가 있으면 처리
  if (n > 1) {
    result -= result / n;
  }

  return result;
}

int main(void) {
  std::ios::sync_with_stdio(false); // 입출력 최적화
  std::cin.tie(NULL);
  std::cout.tie(NULL);

  long long n;
  std::cin >> n;

  std::cout << euler_totient(n) << '\n'; // 결과 출력
  return 0;
}

 

시간 복잡도