백준 1850번: 최대공약수

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

1. 문제

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이 때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

2. 알고리즘

키워드 - 정수론, 유클리드 호제법

문제 이해를 잘 해야 한다. 공약수만큼 1을 출력 하는 문제다.

3. 코드

#include <iostream>
#include <algorithm> // min
#include <math.h>
#include <string>
#include <vector>
 
using namespace std;
 
typedef unsigned long long ull;
ull gcd(ull a, ull b) {
    return (a % b == 0 ? b : gcd(b, a % b));
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);  // scanf 안쓸 경우 쓰세요. Cin 사용시
 
    ull a, b; cin >> a >> b;
    ull sol = gcd(a, b);
    for (int i = 0; i < sol; ++i)
        cout << '1';
 
    return 0;
}