gcd

date: 2021-03-05 excerpt: 最大公約数(greatest common divisor)について

tag: algorithm gcd greatest common divisor python 最大公約数

最大公約数(greatest common divisor)について

概要

共通する最大の約数
lcm(最小公倍数)の導出元になる
- lcm = a*b/gcd(a,b)
２つの差を処理する問題ではユークリッド互除法が前提とされている場合があるため、gcdを一考する余地になる

ユークリッド互除法

最大公約数を求めるにはユークリッド互除法と呼ばれるアルゴリズムで実装されている

再帰を使わない

# a > bである必要がある
a, b = 3918848, 1653264
while b != 0:
    a, b = b, a%b
assert a == 61232, "ユークリッド互除法による結果"

再帰を使う

python

def GCD(a, b):
    if b == 0:
        return a
    return GCD(b, a % b)

C++

#include <cassert>
#include <utility>
using namespace std;
int gcd(int a, int b) {
    if(a < b) swap(a, b);
    if(b == 0)
        return a;
    else
        return gcd(b, a%b);
}

int main() {
    assert(gcd(3918848, 1653264) == 61232);
}

ユークリッド互除法のイメージ

wikipediaから引用

ライブラリを利用する

import math

a, b = 3918848, 1653264
print(math.gcd(a, b))

複数個をまとめて処理する

import numpy as np
N=int(input())
*A,=map(int,input().split())
print(np.gcd.reduce(A))

例

ユークリッド互除法の適応が求められる
- AtCoder Grand Contest 018; A - Getting Difference