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

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

 

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

 

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

 

$$g=gcd(a,b)=gcd(a-b,b)$$

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

 

a 개의 연속된 1이 있는 숫자와 b개의 연속된 1이 있는 숫자 역시 마찬가지죠.  $a>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