[1850] 최대공약수 (C++)

#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
    if (a % b == 0) return b;
    else return gcd(b, a % b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll a, b; cin >> a >> b;
    ll c;

    if (a >= b) c = gcd(a, b);
    else if (a < b) c = gcd(b, a);
    
    for (int i = 0; i < c; i++)
        cout << "1";

    return 0;
}

 

1. 1로 이루어진 수라고 해도, 결국 최대공약수를 구하는 문제이다

ex) a = 6, b = 3인 경우

6 % 3 == 0, GCD = 3

111111 % 111 == 0, GCD = 111

=> 따라서 a와 b의 GCD를 구하고, 그 횟수만큼 1을 출력해주면 되는 간단한 문제이다

2. LCM을 구하는 문제와 같이 재귀함수를 이용한다

 

 

gcd를 계산하는 과정에서 min(a - b, b)을 사용하려 했지만, 잘못된 풀이라 출력 초과가 났던 문제