# 유클리드 호제법

* 두 수의 최대 공약수를 구하는 알고리즘



### 최소 공배수 구하기&#x20;

#### Question - 1934&#x20;

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FlDCX8QP55Qb00PQefghf%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-02%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%203.04.27.png?alt=media\&token=782f572b-ba6d-445a-a040-51913480f1e9)

#### Code

```java
import java.util.Scanner;

public class N21_P1934_최소공배수구하기 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        for (int i = 0; i < N; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int result = a * b / gcd(a, b);
            System.out.println(result);
        }
    }

    public static int gcd(int a, int b) {
        if (b == 0)
            return a;
        else {
            return gcd(b, a % b);
        }
    }
}

```

#### Insight

#### Idea

* 수학
* 정수론
* 유클리드 호제법&#x20;

#### reference



### 최대 공약수 구하기

#### Question - 1850

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FDNXNqLk7HTtBIcmUJIml%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-02%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%203.05.06.png?alt=media\&token=29ce0c6e-48f4-456f-b4ac-a83abc1b45fc)

#### Code

```java
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class N43_P1850_최대공약수_구하기 {

    public static void main(String[] args) throws Exception{
        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);
        }
    }
}

```

#### Insight

* 수의 길이를 나타내는 두 수의 최대 공약수는 A와 B의 최대 공약수의 길이를 나타낸다.
* 즉, 3,6의 최대 공약수 3은 A(111)와 B(111111)의 최대 공약수(111)의 길이로 나타낸다.&#x20;

#### Idea

* 수학
* 정수론
* 유클리드 호제법&#x20;

#### reference



### 칵테일 만들기&#x20;

#### Question - 1033

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FL6QM8uA7VudSFCD7eXRw%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-02%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%203.05.36.png?alt=media\&token=3177144f-ec27-4db7-8775-46b4a0706f49)

#### Code

```java
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class N44_P1033_칵테일_만들기 {

    static ArrayList<cNode>[] A;
    static long lcm;
    static boolean visited[];
    static long D[];

    public static void main(String[] args) throws Exception {
        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 = 1; 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 a, long b) {
        if (b == 0)
            return a;
        else {
            return gcd(b, a % b);
        }
    }

    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;
    }
}
```

#### Insight

#### Idea

* 수학
* 그래프 이론
* 그래프 탐색
* 정수론&#x20;
* 유클리드 호제법&#x20;

#### reference
