Algorithm in A..Z - Euler's phi (오일러 피 함수)

개념

오일러의 피 함수는 N이 주어 졌을 때 1 ~ N의 숫자중 N과 서로소인 숫자의 개수를 찾는 함수이다.

 

---

작동원리

1. p가 소수인 경우

소수인 경우 약수가 1과 자기 자신밖에 없으므로 자기 자신을 제외한 모든 수와 서로소이다.

2. 소수 p의 거듭제곱인 경우

소수 p의 거듭제곱과 서로소가 아닌 경우는 p의 배수일 경우이다. 즉 p, 2p, 3p .... p^(k-1) * p => p^k - p^(k-1)이다.

3. n과 m이 서로소인 경우

n과의 서로소의 곱과 m과 서로소의 곱은 n*m과 서로소이다.

결론

n을 소인수 분해했을 때 p1^a1 * p2^a2 * p3^a3 ... pn^an꼴이 나오면 다음이 성립한다.

 

---

문제

www.acmicpc.net/problem/11689

11689번: GCD(n, k) = 1

---

코드

#include <bits/stdc++.h>
using namespace std;

using Int = int;
using Long = long long;

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

    Long n;
    cin >> n;

    Long ans = n, num = n;
    for (Long i = 2L;i*i <= n;++i) {
        if (num % i == 0) {
            ans /= i;
            ans *= i - 1;

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

    if (num != 1) {
        ans /= num;
        ans *= num - 1;
    }

    cout << ans << "\n";
}