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

Kim Yuhyeon·2022년 4월 18일

cpp 백준 알고리즘

알고리즘 + 자료구조

목록 보기

40/161

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;
}