1850번: 최대공약수

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

1850번: 최대공약수

A와 B의 범위가 long long 안의 자연수이므로 둘을 직접 소인수분해 할 수는 없다. 대신 유클리드 호제법이라는, 빠른 시간 안에 최대공약수를 구할 수 있는 방식으로 구하면 빠르게 구할 수 있다.

 

두 수 A와 B(A > B)에 대해, 두 수가 최대공약수 n을 가지고 있다고 하자.

두 수가 같은 약수를 가지고 있으므로 A와 B는 각각 서로소 a와 b에 대해 an과 bn으로 나타낼 수 있는데, A % B = an % bn = (a % b)n이므로 an과 bn의 최대공약수는 bn과 (a % b)n의 최대공약수이다.

이 과정을 a와 b 둘 중 하나가 0이 될 때까지 진행하면 나머지 하나가 1이 되므로, 즉 A와 B가 n과 0이 되므로 최대공약수 n을 반환해 최대공약수를 구할 수 있다.

#include <cstdio>

typedef long long ll;

// A와 B의 최대공약수를 반환한다
ll gcd(ll A, ll B) {
    if (B == 0) return A;
    else return (B > A) ? gcd(A, B % A) : gcd(B, A % B);
}

int main() {
    // A, B: 최대공약수를 구할 두 수, ans: A와 B의 최대공약수
    ll A, B, ans;
    scanf("%lld %lld", &A, &B);
    
    // A와 B의 최대공약수를 계산해 그만큼 1을 출력한다
    for (ans = gcd(A, B); ans; ans--) printf("1");
    printf("\n");

    return 0;
}