[오일러 Phi 함수] Euler totient function

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

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

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

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

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

    $\varphi (ab)=\varphi (a)\ast \varphi (b)$

 

 

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

$\varphi (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으로 연결되는데, 이는 다음에 알아보도록 하자.