백준 1850 최대공약수 / C++

문제 : 1850

풀이 point

수가 굉장히 크기 때문에 유클리드 호제법을 통해 최대 공약수를 구할 수 있다. 최대 공약수만큼 1을 출력해주면 된다.

코드

//백준 1850, 최대공약수

#include <iostream>

int main (){

    unsigned long long a, b;
    std::cin >> a >> b;

    if(a < b) std::swap(a, b);

    while(b != 0){
        auto c = a % b;
        a = b;
        b = c;
    }

    for(auto i{0}; i<a; ++i){
        std::cout << 1;
    }

    return 0;
}

2025-03-13T05:23:28.610Z