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

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

例:

Input: A = {36, 12, 48}

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

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

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

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

2020年3月20日数学最小公倍数,配列,結合則

配列 a の全ての要素の最小公倍数(LCM: least common multiple) を求めるアルゴリズムについてです。2つの最小公倍数だけではなく、N個の要素の最小公倍数を求めます。

Input: a = {1, ...

2020年3月4日数学約数,競プロ,全列挙

整数 N の約数とは「整数 N を割り切ることができる整数またはその集合」のことです。

単純なアルゴリズムでは約数の全列挙に \(O(N)\) だけかかりますが、約数の性質を活かすと \(O(\sqrt{N})\) で全列 ...

2020年3月1日数学エラトステネスの篩,素因数分解

素因数分解とは「ある自然数を素数の積の形に分解すること」です。

\(12 = 2^2 × 3\)
\(1024 = 2^{10}\)

1つの自然数 n を \(O(\sqrt{n})\) で素因数分解する方法と ...

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

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

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

2 ...

2020年2月29日数学素数,エラトステネスの篩,素数判定

素数とは 「1 より大きい自然数で、正の約数が 1 と自分自身のみであるような数」です。

ある数 \(n\) が素数かどうかを判定するためには、単純に考えると \(O(n)\) の計算量になりますが、後述する通り実は \( ...

2020年2月24日数学bit演算,剰余,競プロ,べき乗,ダブリング,繰り返し二乗法,2進数

多くのプログラミング言語でサポートされてる \(x^n\) を計算する関数のアルゴリズムです。

Input : pow(2,4) (x=2, n=4)
Output : 16

べき乗は非常に大きな数値に ...

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

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

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

2019年12月4日数学剰余,二項係数,テーマ記事,競プロ,素数,逆元

競技プログラミングの問題などでは、二項係数を非常に大きい素数 P で割った余りを出力させる問題が出題されることがあります。 \(P = 1000000007 = 10^9 + 7\) の素数を使用することなどが多いです。

...