오일러 피 함수

Table of Contents

개요

오일러 피 함수 구현

오일러의 정리

문제

1. 개요

 오일러 피 함수는 정수론에 등장하는 함수로서 n 이하의 자연수 중 n과 서로소인 수의 개수를 구하는 함수입니다.  오일러의 정리와 함께 쓰이기도 하고, 단독으로 사용되기도 합니다. 이 글은 독자가 소수를 구하는 알고리즘 중 에라토스테네스의 체를 안다고 가정하고 설명하기 때문에 해당 알고리즘을 모르시는 분은 에라토스테네스의 체 설명을 보고 오시는 걸 추천합니다.

2. 오일러 피 함수 구현

 오일러 피 함수란, n 이하의 자연수 중 n과 서로소인 수의 개수를 구하는 함수입니다. n의 소인수 p들에 대해서 아래의 식을 계산하면 오일러 피 함수 값을 얻을 수 있습니다.

 위의 식을 구현하기 편하게 정리하면 아래와 같이 됩니다. n을 각각의 항에 나누어서 뿌린 꼴이지요.

 이 때, k 는 p^k 가 n의 약수가 되는 최댓값입니다.

 n = 12 라면,

12 = 2^2 * 3

-> 오일러 함수 = (2^2 - 2^1) * (3^1 - 3^0) = (4-2) * (3-1) = 4 로 계산할 수 있습니다.

 12와 서로소인 것은 { 1, 5, 7, 11 } 이렇게 4개이므로 제대로 계산된 것을 알 수 있습니다. 식에 있는 그대로 n 의 소인수들을 구해서 각각의 p^k를 계산하면 끝이므로 아래와 같이 간단하게 구현할 수 있습니다.

// code by RiKang, weeklyps.com
using namespace std;
#define PN 1000000
 
bool isprime[PN+5];
vector<long long> prime;
void primechk(){
    for(int i=2;i<=PN;i++) isprime[i] = true;
    for(long long i=2;i<=PN;i++)
        if(isprime[i]){
            prime.push_back(i);
            for(long long j=i*i;j<=PN;j+=i)
                isprime[j] = false;
        }
}
 
// 오일러 파이 함수 = v 와 서로소인 수의 갯수 return
 
long long euler(long long v){
    long long ret=1;
    for(auto now: prime){
        long long p=1;
        while(v%now==0){
            v/=now;
            p*=now;
        }
        if(p!=0){
            ret*=(p-(p/now));
        }
    }
    if(v!=1) ret*=(v-1);
    return ret;
}
 

3. 오일러의 정리

 오일러 피 함수를 활용하는 대표적인 정리입니다. a와 n 이 서로소인 자연수들이라면, 아래와 같은 식이 성립합니다. 페르마의 소정리의 확장판같은 의미도 있기 때문에, 프로그래밍 문제에 출제되기도 합니다.

${\displaystyle a^{\phi (n)}\equiv 1{\pmod {n}}}$

4. 문제

(0) [CF 400 E] The Holmes Children

※ 본문의 코드들은 C++ 17 환경에서 작성되었습니다.

※ 문의 : rikang93@gmail.com