[BaekJoon][1850] 최대공약수

BAEKJOON ONLINE JUDGE

1850 최대공약수

https://www.acmicpc.net/problem/1850

이 문제는 약간 함정이다.

입력받은 A와 B로 1로만 만들어진 수를 만든 다음 최대공약수를 구하려 했는데 수가 너무 커서 결과를 구할 수 없었다.

문제를 풀던 도중 규칙을 찾은 것이

결국 1의 개수의 최대공약수가 결과 수의 1의 개수라는 것이었다.

따라서 A와 B의 GCD를 구한 후 이 수만큼의 1을 출력하면 되는 문제

#include <stdio.h>
 
long long int gcd(long long int n, long long int m)
{
    if (m == 0)    return n;
    return gcd(m, n % m);
}
 
int main()
{
    long long int a, b;
 
    scanf("%lld %lld", &a, &b);
 
    for (int i = 1; i <= gcd(a, b); i++) {
        printf("1");
    }
    printf("\n");
 
    return 0;
}