[백준] 1850번: 최대공약수

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

문제

알고리즘 접근 방법

3과 4의 최대공약수가 1이면 답은 1,
3과 6의 최대공약수가 3이면 답은 111이다.
그래서 먼저 입력받은 두수의 최대공약수를 구하고
그 수만큼 1을 출력한다.
입력되는 값이 2^63이므로 long long 타입으로 했다.

풀이

#include <iostream>

using namespace std;

long long gcd(long long a, long long b){
    while(b > 0){
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

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

    long long A, B;
    cin >> A >> B;

    long long result = gcd(A, B);

    for (long long i=0; i<result; i++)
        cout << 1;
    cout << '\n';
    
    return 0;
}

정리

3을 111로 바꾸고 4를 1111로 바꿔서
111과 1111의 최대공약수를 구하려고 했는데,
그렇게 했다가 메모리 초과 났다 !! ㅠ 조심

증명글 봤는데 이해는 잘 안감. .

💡 참고 포스팅

백준 1850 : 1로만 된 최대공약수
ziwonii25님 블로그