C# [백준 BAEKJOON] 2824번 최대공약수

문제

상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다.

상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다.

이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다.

셋째 줄에 M(1 ≤ M ≤ 1000)이 주어진다. 넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, M개의 수를 곱하면 B가 된다.

 

출력

두 수의 최대공약수를 출력한다. 만약, 9자리보다 길다면, 마지막 9자리만 출력한다. (최대 공약수가 1000012028인 경우에는 000012028을 출력해야 한다)

 

2824번: 최대공약수

 

 

풀이 코드

using System;
using System.Numerics;

class Program
{
    static void Main(string[] args)
    {
        var count1 = Console.ReadLine();

        var input1 = Console.ReadLine().Split();
        var num1 = new BigInteger(1);

        for (int i = 0; i < input1.Length; i++) 
        {
            num1 *= BigInteger.Parse(input1[i]);
        }

        Console.ReadLine();

        var input2 = Console.ReadLine().Split();
        var num2 = new BigInteger(1);

        for (int i = 0; i < input2.Length; i++)
        {
            num2 *= BigInteger.Parse(input2[i]);
        }

        var result = gcd(num1, num2).ToString();
        if (9 < result.Length)
        {
            Console.WriteLine(result.Substring(result.Length - 9));
        }
        else
        {
            Console.WriteLine(result);
        }
    }

    static BigInteger gcd(BigInteger n, BigInteger m)
    {
        while(0 < m)
        {
            var r = n % m;
            n = m;
            m = r;
        }

        return n;
    }
}

 

함께 보면 좋은 문제

C# [백준 BAEKJOON] 13277번 큰 수 곱셈