整数の最大公約数と最小公倍数の効率的計算手法
整数の最大公約数（GCD）と最小公倍数（LCM）は数論の基礎概念であり、暗号アルゴリズムや最適化処理で頻繁に利用される。GCDは共通の約数の最大値、LCMは共通の倍数の最小値を指す。これらの値は a × b = GCD(a,b) × LCM(a,b) の関係で結ばれ、GCDを先に求めることでLCMを効率的に導出できる。
標準ライブラリを活用する方法（C++17以降）
C++17では<numeric>ヘッ ...
7月8日 20:53 投稿
最大公約数と最小公倍数のアルゴリズム
最大公約数 (GCD)
2つの整数 a と b の最大公約数（GCD）とは、両方を割り切ることができる最大の整数を指します。記号では gcd(a, b) と表されます。
例えば、gcd(15, 18) と gcd(-15, -18) はどちらも 3 になります。
ユークリッドの互除法
最大公約数を求める代表的な方法として、ユークリッドの互除法が知られています。
このアルゴリズムの仕組み：
大きい数を小 ...
5月17日 14:51 投稿