[白俊]1850号:最大公約数

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

質問する

アルゴリズムアクセスメソッド

3と4の最大公約数が1であれば、答えは1です.
3と6の最大公約数が3であれば、答えは111です.
入力した2つの数の最大承諾数を求めます.
その数で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;
}

整理する

3を111に、4を1111に
111と1111の最大承諾数を求めたかったのですが、
そうするとメモリオーバー!!気をつけて
証明書を見ましたが、よく理解しています.

💡 注意:配置

白駿1850:1の最大公約数
ziwonii 25のブログ