백준 C# - 9613 +) 풀이 (유클리드 호제법)

문제를 풀기전에 이해 부터 하자

01 문제 잘 읽자

두번째 줄의 첫번째수도 최대 공약수에 포함되어있는지 수인줄 알고 문제 풀다가 최대 공약수가 예제 출력이랑 왜 안맞지..? 최대 공약수 구하는 방법이 틀렸나 했는데 각 테이스 케이스 개수를 구하는 거였다😂 

3 // 전치 테스트 케이스의 개수
4 10 20 30 40 // 맨 앞에 수는 각 테스트 케이스 그러므로 4개의 테스트 케이스
3 7 5 12
3 125 15 25

---

02 long 사용

N=100이고 모든 수가 100만일때 모든 쌍의 최대공약수 합이 int 값의 범위를 초과하는 경우가 있으므로 long을 사용해야 한다.

---

문제를 풀다가 반복문이 너무 많이 나와서 뭔가 잘못됐다라는 느낌을 받았다. 그래서 좋은 방법이 없을까 찾아보다가 유클리드 호제법을 찾게되었다.

 

유클리드 호제법

두 양의 정수의 최대 공약수를 구하는 방법이다. 최대 공약수는 두 수 이상의 여러 공통된 약수 중 최대인 수이다.

1. 큰수를 작은 수로 나눈다.

2. 나누는 수를 나머지로 계속 나눈다. 나머지가 0이 나오면 나누는 수가 최대 공약수이다.

---

예제

코드 예시

static long GCD(long a, long b)
{
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

 

a가 1512이고 b가 1008인 경우

초기 상태: a = 1512, b = 1008

1회 반복: temp = 1008, b = 1512 % 1008 = 504, a = temp = 1008

2회 반복: temp = 504, b = 1008 % 504 = 0, a = temp = 504
b가 0이 되면 반복 종료, 최대공약수는 504

---

코드 전문

using System;
namespace baek2
{
    class Program
    {
        static long GCD(long a, long b)
        {
            while (b != 0)
            {
                long temp = b;
                b = a % b;
                a = temp;
            }
            return a;
        }
        static void Main(string[] args)
        {
            long testcase = int.Parse(Console.ReadLine());

            for (int i = 0; i < testcase; i++)
            {
                string[] t = Console.ReadLine().Split();
                int n = int.Parse(t[0]);
                long total = 0;
                for (int z = 1; z <= n; z++)
                {
                    for (int y = z + 1; y <= n; y++)
                    {
                        long a = int.Parse(t[z]);
                        long b = int.Parse(t[y]);
                        long gcd = GCD(a, b);                    
                        total += gcd;
                    }
                }
                Console.WriteLine(total);
            }
        }
    }
}