[21603][白俊/BOJ]1800号最大公約数

840 ワード
アルゴリズム#アルゴリズム# テキストリンク

質問する



にゅうしゅつりょく



に答える


Aが111、Bが1111の場合、最大承諾数は1である.
Aは1111,Bは11111で最大公約数は111である.
したがって,ユークリッドアーク除算法で最大公約数を求め,最大公約数で1を出力すればよい.
入力した数字は2^63未満なので、int型の代わりにlong long型を使用します.

コード#コード#

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b)
{
    ll r;
    while (b != 0) 
    { 
        r = a % b; 
        a = b; 
        b = r; 
    } 
    return a;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll a, b;
    cin >> a >> b;

    for (int i = 0; i < gcd(a, b); ++i)
        cout << '1';
}
BOJ 2146ブリッジの作成
[アルゴリズム解析]BOJ 12865普通リュックサック