2020年3月21日数学最大公約数,配列,結合則

配列 A が与えられて、その全ての要素の最大公約数(GCD)を求めることを考えます。2つの最大公約数だけではなく、N個の要素の最大公約数を求めます。

例:

Input: A = {36, 12, 48}

2020年3月21日数学最大公約数,ユークリッドの互除法,拡張ユークリッドの互除法,1次方程式

最大公約数を求める高速なアルゴリズムとしてユークリッドの互除法が知られています。このユークリッドの互除法を拡張することにより、

$$ ax+by=gcd(a,b)$$

の形をした、2変数の一次方程式の整数解を求 ...

2020年3月1日数学最大公約数,競プロ,ユークリッドの互除法,最小公倍数

最小公倍数(LCM: least common multiple) とは、「0でない複数の自然数の公倍数のうち最小の自然数」のことを言います。

最小公倍数は、最大公約数を利用することで簡単に求めることができます。

2 ...

2020年1月26日AtCoder操作,最大公約数,不変量,最大値,500点,約数

問題へのリンク

問題概要

N 個の整数列 \(A_1, A_2, \cdots, A_N\) に、以下の操作をK回まで行う。これら全てはある数の倍数となるが、その数の最大値を求めよ。

操作:\(A_1, A_2, ...

2019年12月6日数学最大公約数,競プロ,ユークリッドの互除法,拡張ユークリッドの互除法

2つの整数の最大公約数を求める際、単純に素因数分解して、共通部分を求めようとすると時間がかかってしまいます。

このような時に、対数のオーダーで高速に最大公約数を求めるアルゴリズムとして、ユークリッドの互除法が古くから知られ ...