[백준] 2824 - 최대공약수

1. 문제

2824번: 최대공약수

2. 개요

A와 B 각각 N, M개의 약수가 주어진다.

A, B의 최대공약수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

주어진 수들을 모두 곱하여 A, B를 구한 뒤 최대공약수를 구하면 된다.

Python은 딱히 오버플로우 발생이 없지만,

C#의 경우 long, ulong을 쓴다 하더라도 범위를 벗어나 오버플로우가 발생하는 경우가 있다.

인수분해를 통해 해결할 수도 있지만 Biginteger를 이용해 이를 더 간단히 해결할 수 있다.

3-2. Python

import sys
import math

a, b = 1, 1

N = int(sys.stdin.readline())
n = list(map(int, sys.stdin.readline().split()))

for i in range(N):
    a *= n[i]

M = int(sys.stdin.readline())
m = list(map(int, sys.stdin.readline().split()))

for i in range(M):
    b *= m[i]

gcd = str(math.gcd(a, b))
print(gcd[-9:])

3-3. C#

using System.Numerics;

namespace boj_2824
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            BigInteger a = 1, b = 1;

            int N = int.Parse(sr.ReadLine());
            BigInteger[] n = Array.ConvertAll(sr.ReadLine().Split(), BigInteger.Parse);

            for (int i = 0; i < N; i++)
                a *= n[i];

            int M = int.Parse(sr.ReadLine());
            BigInteger[] m = Array.ConvertAll(sr.ReadLine().Split(), BigInteger.Parse);

            for (int i = 0; i < M; i++)
                b *= m[i];

            string gcd = GCD(a, b).ToString();

            if (gcd.Length > 9)
                sw.WriteLine(gcd[^9..]);

            else
                sw.WriteLine(gcd);

            sw.Close();
        }

        static BigInteger GCD (BigInteger first, BigInteger second)
        {
            while (first != 0 && second != 0)
            {
                if (first > second)
                {
                    first %= second;
                }

                else
                {
                    second %= first;
                }
            }

            return first == 0 ? second : first;
        }
    }
}