[BOJ/백준][Silver1] 1850 : 최대공약수 (C++)

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

1850번: 최대공약수

 

 

[난이도] Silver1
[유형] 수학

[풀이]
1의 개수끼리 최대 공약수를 구한 뒤,
이 수만큼 1을 출력해주면 정답이라고 합니다.
증명은 못하겠어서 gcd 구하는 연습용으로 풀었습니다..

 

 

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
ll a,b;
ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    while(b!=0){
        ll c = a%b;
        a=b;
        b=c;
    }
    return a;
}
int main(){
    scanf("%lld%lld",&a,&b);
    for(int i=0;i<gcd(a,b);i++) printf("1");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/1850.cpp