[오일러 Phi 함수] Euler totient function

 오일러 Phi 함수 $\phi(n)$ 는 1부터 n까지 사이의 수 중에서 n과의 최대공약수가 1인 수의 갯수를 나타내는 함수이다. Phi 함수는 아래와 같은 성질을 만족한다.

 1) 만약 p가 소수라면 $\phi(p)$ = p-1 를 만족한다. 

 2) 만약 p가 소수이고, k$\geq1$라면 1부터 $p^k$까지 정확히 $p^k/p$가 p로 나누어지기 때문에 다음을 만족한다.

    $\phi(p^k) = p^k - p^{k-1}$

 3) a와 b가 서로소라면 다음을 만족한다.

    $\phi(ab) = \phi(a) * \phi(b)$

 

 

 이를 바탕으로 수식을 정리하면, 아래와 같다. 

$\phi(n)$ = n * $(1- \frac{1}{p_1})$* $(1- \frac{1}{p_2})$* $(1- \frac{1}{p_3})$ ... * $(1- \frac{1}{p_k})$

 

 코드로 표현하면, 아래와 같은데, 이는 Euler totient function의 정의를 물어보는 백준 11689 문제를 풀 수 있게 된다. 

ll phi(ll n) {
    ll result = n;
    for(ll i=2;i*i<=n;++i) { // ll 형으로 표현하지 않으면 int형의 한계로 무한히 반복하게 됨
        if(n%i==0) {
            while(n%i==0) n /= i;
            result -= result / i;
        }
    }
    if(n>1) {
        result -= result/n;
    }
    return result;
}

int main() {
    fastio;
    ll n;
    cin >> n;
    ll ans = phi(n);
    cout << ans << '\n';
    return 0;
}

 사실 Euler totient function의 진정한 면목은 페르마의 소정리와 연결되는 Euler Theorem으로 연결되는데, 이는 다음에 알아보도록 하자.