[C/C++] 백준 #1850 최대공약수(수학)

이번문제는 문제를 살짝 꼬았지만, 결국 최대 공약수를 구하는 문제입니다.

 

유클리드 호제법을 이해하고 있다면, 이 문제를 쉽게 풀 수 있습니다.

 

유클리드 호제법에서 큰수에서 작은수로 나눈 나머지를 가지고 우리는 최대 공약수를 구할 수 있습니다.

 

\[ g = gcd(a, b) = gcd(a-b, b) \]

형태가 성립하기 때문이죠.  위식에서는 뺄셈을 했지만, 나눈 나머지를 해도 됩니다.

 

a 개의 연속된 1이 있는 숫자와 b개의 연속된 1이 있는 숫자 역시 마찬가지죠.  \(a \gt b\)라고 한다면, a개의 연속된 1이 있는 숫자를 b개의 연속된 1이 있는 숫자로 나눈 나머지는 a를 b로 나눈 나머지의 개수만큼 1이 연속된 수가 됩니다.

 

예를 들어서 5개의 1이 연속된 11111 과 3개의 1이 연속된 111의 나머지는 2개의 연속된 1이 있는 숫자인 11이 된다는 것이죠.

 

이를 이용하면 손쉽게 풀 수 있는 문제입니다

 

아래는 제가 작성혼 소스입니다.  참고용으로 봐주세요.

//--------------------------------------------------------------------
//    baekjoon #1850 - Greatest Common Divisor
//        - by Aubrey Choi
//        - created at 2019-06-16
//--------------------------------------------------------------------
#include <stdio.h>

int gcd(long long a, long long b)
{
    while(b)
    {
        long long t = b;
        b = a % b;
        a = t;
    }
    return (int)a;
}

int main()
{
    long long a, b;
    scanf("%lld%lld", &a, &b);
    int g = gcd(a, b);
    while(g--) putchar('1'); putchar('\n');
}

greatest common divisor