[白俊]2609号:最大公倍数と最小公倍数

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

質問する

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

最大公約数GCD
最大承諾数は、2つの自然数の共同薬水の中で最大の数を意味する.
ex)72と30の最大承諾数は6です.
最小公倍数LCM(Least Common Multiple)
最小公倍数は、2つの自然数の最小公倍数を意味します.
最小公倍数=2つの自然数の積/最大公倍数
ex)72および30の最小公倍数は360である.
2つの自然数の最大承諾数を得るために.
2から2つの自然数のうちの小さな自然数を分けることができ,最大の公約数が得られる.
上記の方法で問題を解くと.
時間複雑度はO(N)であった.
これは悪い方法ではありませんが、効率を高めるために
ユークリッドアーク除去アルゴリズムを使用すると
時間の複雑さはO(logN)に減少することができる.
ユークリッドアルゴリズム
2つの自然数a,bについて
aをbで割った残りの部分をr(ただしa>b)と呼ぶと、
aおよびbの最大公約数は、bおよびrの最大公約数に等しい.
この性質に基づいて、bをrで割った残りのr 0を求める.
rをr 0で割った残りの値を求めるプロセスを繰り返す.
残りが0の場合の除算数
aとbの最大公約数.
これは最も古いアルゴリズムです.
紀元前300年頃のユークリッドの『概論』第7巻に相当し、命題1から3

ex.10と8の最大公約数?
1. a = 10, b = 8
GCD(10, 8) = GCD(8, 10%8) = GCD(8, 2)
2. a = 8, b = 2
8%2 = 0 -> GCD = 2

に答える

#include <iostream>

using namespace std;

int gcd(int a, int b){
    while(b > 0){
        int temp = b;
        b = a%b;
        a = temp;
    }

    return a;
}

int lcm(int a, int b){
    return (a*b)/gcd(a, b);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int A, B;

    cin >> A >> B;

    cout << gcd(A, B) << '\n';
    cout << lcm(A, B) << '\n';
    return 0;
}

整理する

ユークリッド号記憶行~

💡 注意:配置

コードZamongブログ
Dreamyブログ