[알고리즘] 정수론 - 오일러 피와 유클리드 호제법

정수론을 제대로 파고자 한다면 그 범위가 만만찮다.

하지만, 코딩 테스트에 나오는 일반적인 유형이라는게 존재하기에 그 대표적인 경우들을 대처할 수 있다.

 

 

그 중 많이 쓰이는 것은 유클리드 호제법(확장도 있다)이다.

물론 오일러 피 함수도 간혹 쓰이나 유클리드 호제법에 비할 바는 아니다.

그 이유는 유클리드 호제법이 최대 공약수와 최소 공배수를 구하는 정말 효율적인 방법이기 때문이다.

 

 

 

오일러 피 함수

 

오일러 피 함수는 1부터 N까지의 범위에서 N과 서로소인 자연수의 개수를 뜻한다.

실제 코딩 테스트에서 사용되는 구현 부분만 짚고 넘어갈 것이기에 간단하게 핵심 원리만 알아보자.

 

1. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화 한다.

2. 2부터 시작하여, 현재 배열의 값과 인덱스가 같다면(소수라면) 현재 선택된 숫자의 배수에 해당하는 배열을 끝까지 탐색하여 P[i] = P[i] - P[i]/k 연산을 수행한다.

3. 배열을 끝까지 2번과정을 반복하여 오일러 피 함수를 완성할 수 있다.

 

 

 

과정 자체가 에라토스테네스의 체와 비슷하다.

다만, 걸러내는 부분이 P[i] = P[i] - P[i] / k 연산이 들어간 것만 다르다.

 

수학적인 측면에서 간단하게 이해한 바로는,

"P[i]는 그 수 이하에서 서로소가 안되는 후보를 전부 지워내어, 실제로 서로소가 되는 개수"

라고 이해할 수 있었다.

 

 

 

 

 

오일러 피 함수 예시

 

11689번: GCD(n, k) = 1

 

문제에서 요하는 GCD(n, k) = 1의 의미는 최대 공약수가 1밖에 없는 것으로, 서로소임을 뜻한다.

즉, 오일러 피 함수를 사용하라고 대놓고 말하고 있는 것이다.

 

 

 

 

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        long result = n;
        for(long p=2; p<=Math.sqrt(n); p++) {
            if (n % p == 0) {
                result = result - result / p;
                while(n % p == 0) {
                    n /= p;
                }
            }
        }

        if (n > 1) {
            result = result - result/n;
        }
        System.out.println(result);

    }
}

 

- 현재 값이 소인수인지 확인하기 위해 n%p == 0인지 확인해준다.

- 소인수라면, 값을 result = rsult - result / p로 업데이트 해주어 서로소가 안되는 값을 소거해준다.

- while(n % p == 0)을 통해서 n값의 p 소인수 내역을 없애준다.

- n > 1은 아직 소인수 내역이 남아 있는 것인데, 이는 n자기 자신이므로, 빼주면 된다.

 

 

 

 

 

 

유클리드 호제법

 

유클리드 호제법은 최대 공약수를 구할 수 있는 아주 효율적인 방법이다.

또한 구해낸 최대 공약수를 통해 최소 공배수를 쉽게 구할 수도 있다.

 

1850번: 최대공약수

 

 

import java.nio.Buffer;
import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long a = sc.nextLong();
        long b = sc.nextLong();

        long result = gcd(a, b);
        while(result > 0) {
            bw.write("1");
            result--;
        }
        bw.flush();
        bw.close();
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }

        else {
            return gcd(b, a%b);
        }
    }
}

 

- 위의 gcd 함수의 꼴은 유클리드 호제법을 사용하는 구현에 해당하는 부분이므로 꼭 기억해 두자

 

 

 

 

 

 

유클리드 호제법 예시 문제

 

 

최소 공배수만을 구하는 문제는 몇 없을 것이다.

실제로는 다양한 알고리즘 전략들 사이에서 이러한 유클리드 호제법을 사용하는 경우가 많다.

아래 예시 문제를 통해 유클리드 호제법을 제대로 사용해보자.

 

1033번: 칵테일

 

이 문제는 칵테일의 질량 비율을 구하고, 최소 질량을 구하는 문제이다.

해결하기 위한 방법으로는, 그래프 관점에서 사이클이 없는 트리 구조를 생각해야 한다.

그 구조를 바탕으로 DFS를 진행하는데, 이 과정에서 유클리드 호제법을 사용하는 것이다.

 

import java.nio.Buffer;
import java.util.*;
import java.io.*;

public class Main {
    static ArrayList<cNode>[] A;
    static long lcm;
    static boolean visited[];
    static long D[];
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = sc.nextInt();
        A = new ArrayList[N];
        visited = new boolean[N];
        D = new long[N];

        lcm = 1;
        for(int i=0; i<N; i++) {
            A[i] = new ArrayList<cNode>();
        }
        for(int i=0; i<N-1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int p = sc.nextInt();
            int q = sc.nextInt();

            A[a].add(new cNode(b, p, q));
            A[b].add(new cNode(a, q, p));
            lcm *= (p*q / gcd(p, q));
        }
        D[0] = lcm;
        DFS(0);
        long mgcd = D[0];
        for(int i=0; i<N; i++) {
            mgcd = gcd(mgcd, D[i]);
        }
        for(int i=0; i<N; i++) {
            System.out.print(D[i] / mgcd + " ");
        }
    }

    public static long gcd(long p, long q) {
        if (q == 0) {
            return p;
        } else {
            return gcd(q, p%q);
        }
    }
    public static void DFS(int Node) {
        visited[Node] = true;
        for(cNode i : A[Node]) {
            int next = i.getB();
            if (!visited[next]) {
                D[next] = D[Node] * i.getQ() / i.getP();
                DFS(next);
            }

        }
    }

}

class cNode {
    int b;
    int p;
    int q;
    public cNode(int b, int p, int q) {
        super();
        this.b = b;
        this.p = p;
        this.q = q;
    }
    public int getB() {
        return b;
    }
    public int getP() {
        return p;
    }
    public int getQ() {
        return q;
    }
}

 

 

- 노드에 비율 정보를 담기 위해서 cNode 클래스를 만들었다.

- DFS를 진행하며, 주어진 비율로 다음 노드 값을 갱신한다.

- 최소 공배수는 두 수의 곱을 최대 공약수로 나눈 것이다.

- DFS를 이용해 업데이트 된 D 배열의 값들의 최대 공약수를 계산한다.

 

 

 

 

 

 

확장 유클리드 호제법

 

확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것이다.

그러면 왜 유클리드 호제법은 최대 공약수를 구하는 방법이라고 하는 것인가. 서로 의미가 상충되지 않느냐 할 수 있다.

 

확장의 차이는 바로 방정식의 해를 구하는데, 최대 공약수를 구하는 알고리즘이 쓰인다는 것이다.

ax + by = c에서 c% gcd(a, b) = 0인 경우에 정수 해를 가진다.

다시말해, c가 a와 b의 최대 공약수의 배수인 경우에만, 정수해를 가진다는 것이다.

 

 

확장 유클리드 호제법은 a와 b에 대해 기존의 유클리드 호제법과 마찬가지로 나머지가 0이 될때까지 계속 % 연산을 해준다.

다만, 반복으로 구한 나머지와 몫을 이용하여, 거꾸로 올라가며 새로운 연산을 한다는 것이 다르다.

x = y`
y = x` - y`*q

 

`은 각각 이전 x와 이전 y를 뜻한다. q는 몫이다.

처음 시작하는 이전 x와 y는 각각 1과 0으로 지정한다.

 

이렇게 구한 최종 x와 y는 ax + bt = gcd(a, b)를 만족하는 값이라는 것이다.

* 만약 오른쪽 변의 값이 gcd(a, b)의 배수가 아니라면, x와 y의 값의 범위는 정수 범위가 아닐 것이다.

 

 

21568번: Ax+By=C

import java.nio.Buffer;
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st =new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        long gcd = gcd(a, b);
        if (c % gcd != 0) {
            System.out.println(-1);
        } else {
            int mok = (int) (c / gcd);
            long[] ret = Excute(a, b);
            System.out.println(ret[0] * mok + " " + ret[1] * mok);
        }
    }

    public static long[] Excute(long a, long b) {
        long[] ret = new long[2];
        if (b == 0) {
            ret[0] = 1;
            ret[1] = 0;
            return ret;
        }
        long q = a / b;
        long[] v = Excute(b, a%b);
        ret[0] = v[1];
        ret[1] = v[0] - v[1] * q;
        return ret;
    }
    public static long gcd(long a, long b) {
       while(b != 0) {
           long temp = a % b;
           a = b;
           b = temp;
       }
       return Math.abs(a);
    }
}

 

- 반복문 형태로 gcd를 구현할 수도 있다.

- Excute 함수를 통해 나머지가 0에 도달한 경우 x`=1, y`=0으로 설정한다.

- 재귀 함수 형태로 Excute를 실행하고, 연산하여 최종 x와 y의 값을 구한다.

- c / gcd만큼의 값을 최종 x와 y에 곱한다.

 

 

Reference

 

- Do it! 코딩 테스트 - 기본 편