[BOJ/C++] 11689 GCD(n, k) = 1

오일러 피

오일러 피 함수 $P[N]$은 1~N까지 범위에서 N과 서로소인 자연수의 개수를 뜻합니다.

오일러 피 함수의 원리

1. 구하고자 하는 오일러 피의 범위만큼 배열을 자기 자신의 인덱스 값으로 초기화한다.
2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열의 끝까지 탐색하며 $P[i]=P[i]-P[i]/K$ 로 업데이트 해줍니다.
   • 에라토스테네스의 체에서 배수를 지우는 부분을 $P[i]=P[i]-P[i]/K$로 변경한 것으로 생각해도 됩니다.
3. 배열의 끝까지 2를 반복합니다.

예시

• N이 6이라면
• 서로소가 될 수 있는 후보의 개수로 초기화 (1, 2, 3, 4, 5, 6)
• 2의 배수로 인한 탈락 $P[6] = P[6] - P[6]/2$ -> 6 - 6/2 = 3 이고 이때 서로소는 (1, 3, 5)
• 3의 배수로 인한 탈락, P[6]이 3으로 업데이트 되었기 때문에 3 - 3/3 = 2 이고 이때 서로소는 (1, 5)
• 삭제하는 기준을 6이 아닌 업데이트 된 3으로 진행하는 이유는 3과 2의 공배수는 이미 2의 배수에서 삭제되었기 때문에 중복 삭제를 방지하기 위함입니다.
• 이때 2의 의미는 숫자 6과 6이하의 숫자 중 서로소가 되는 개수가 2라는 의미입니다.

오일러 피 함수 문제는 자주 나오진 않지만 원리만 간단히 알아보면 좋을 것 같습니다

해당 문제에서 $GCD(n, k) = 1$ 을 만족하는 자연수의 개수가 바로 오일러 피 함수의 정의입니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    long N;             // 소인수 구성
    cin >> N;

    long result = N;    // 서로소의 개수

    for(long i=2; i<=sqrt(N); i++)
    {
        if(N%i == 0)    // 소인수라면
        {
            result = result - result / i;   // 결과값 업데이트
            while (N % i == 0)  
                N /= i;     // 소인수 지우기, 2^7*11 이라면 11만 남긴다.
        }
    }

    // 아직 소인수 구성이 남아있다면
    // 반복문에서 제곱근까지만 탐색하기 때문에 1개의 소인수가 누락되는 케이스
    if (N > 1)
        result = result - result / N;

    cout << result;

    return 0;
}