gcdとlcmの実装
最大公約数（GCD : Greatest Common Divisor）と最小公倍数（LCM : Least Common Multiple）を求めるプログラムをc言語で書いてました。競プロ（AtCoder）で使うためです。最近使用言語をc++に乗り換えたのでcからc++に書き換えていたら色々と発見があったので記録しておきます。
最大公約数 gcd
まずは2つの数で。
これは、ユークリッドの互除法を用いて求めます。詳しくはユークリッドの互除法 - Wikipedia参照。
//cでもc++でも int gcd(int a, int b){ if(a%b == 0){ return b; }else{ return gcd(b, a%b); } }
ときどき、$a > b$ が必要だとして関数の冒頭でif(a < b)swap(a, b)みたいなことをやっているのを見ますが、これは必要ないです。
$a < b$ のときa % b == aなので結局gcd(b, a)に帰結します。
最小公倍数 lcm
これは、gcdとlcmの関係を用いて求めます。
正の整数 $a,b$ に対して，それらの最大公約数を $\mathrm{gcd}(a,b)$ ，最小公倍数を $\mathrm{lcm}(a,b)$ とおくと $$ab=\mathrm{gcd}(a,b)\cdot\mathrm{lcm}(a,b)$$ 最大公約数と最小公倍数の積の性質の２通りの証明 | 高校数学の美しい物語より改変
つまり、$$\mathrm{lcm}(a,b) = \frac{ab}{\mathrm{gcd}(a,b)}$$ということです。
//cでもc++でも int lcm(int a, int b){ return a*b / gcd(a, b); }
もちろん関数gcdは先述のように定義済み
3つ以上の整数についてのgcdとlcm
説明は省きますが（検索してください）3つ以上の整数についてのgcdやlcm以下のようになります。 \begin{align} \mathrm{gcd}(a,b,c) = \mathrm{gcd}\big( a, \mathrm{gcd}(b,c) \big) \cr \mathrm{lcm}(a,b,c) = \mathrm{lcm}\big( a, \mathrm{lcm}(b,c) \big) \end{align} 整数が増えても同様に、2つずつ処理をしていけば全体のgcd、lcmを求めることができます。
gcd
ということで、正の整数の配列を受け取って全体のgcdを求める関数は次のようになります。cでは、配列を渡す時のお馴染みですが要素数も渡す必要があります。
//c int gcd_arr(int a[], int n){ if(n==2){ return gcd(a[0], a[1]); }else{ a[n-2] = gcd(a[n-2], a[n-1]); /* 後ろの2つをgcd処理 */ } return gcd_arr(a, n-1); /* 再帰する */ } }
よく考えたら再帰する必要ないじゃんってなったのでループで解決するのをc++で。
//c++ int gcd_arr(vector<int> &a){ int n = a.size(); for(int i=n-2; i>=0; i--){ a[i] = gcd(a[i], a[i+1]); } return a.front(); }
lcm
同じくlcmを求める関数は…………gcdをlcmに書き換えるだけですが、cでのループ版とc++での再帰版を示すために書いてみましょう
//c int lcm_arr(int a[], int n){ for(int i=n-2; i>=0; i--){ a[i] = lcm(a[i], a[i+1]); } return a[0]; }
//c++ int lcm_arr(vector<int>& a){ int n = a.size(); if(n==2){ return lcm(a[0], a[1]); }else{ a[n-2] = lcm(a[n-2], a[n-1]); a.pop_back(); return lcm_arr(a); } }
注意点
gcd_arrとlcm_arrは、渡された配列を直接操作することに注意してください
実用
入力は、空白区切で数字を受け付けて、正でない数が来たら締め切って処理することにしました。（cだと先に要素数を入れないと色々と面倒な気がします）
//c++ #include <bits/stdc++.h> using namespace std; int gcd(int a, int b){/*略*/} int lcm(int a, int b){/*略*/} int gcd_arr(vector<int> &a){/*略*/} int lcm_arr(vector<int> &a){/*略*/} int main(){ vector<int> array; int buf; cin >> buf; while( buf > 0 ){ array.push_back( buf ); cin >> buf; } //array = {24,18,42,12} としたとき vector<int> copy; copy = array; cout << "gcd = " << gcd_arr( copy ) << endl; //copy = {6,6,6,12}になってる copy = array; cout << "lcm = " << lcm_arr( copy ) << endl; //copy = {504,252,84,12}になってる }
先述の通り、gcd_arr lcm_arrに配列を渡すと配列の中身が変更されるので、一旦別のところにコピーしてから使います。
$$ \mathrm{gcd}(24, 18, 42, 12)=6 と \mathrm{lcm}(24, 18, 42, 12)=504 $$
を求めたいとき、標準入力は
24 18 42 12 0
とし、出力は次のようになります。
gcd = 6 lcm = 504
c++17では……
冒頭でgcdとlcmを実装しましたが、c++17ではstd::gcdとstd::lcmが用意されています。
#include <numeric> std::gcd(a, b); std::lcm(a, b);
AtCoderでも、C++ (GCC 9.2.1)で使えます。
おしまい。
参考
- 個人的メモ
$ c++ -v Apple clang version 11.0.0 (clang-1100.0.33.17) Target: x86_64-apple-darwin18.7.0 Thread model: posix InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin
make をそのまま使うと
$ make ./test
c++ -I .../@AtCoder test.cpp -o test
test.cpp:5:20: error: a space is required between consecutive right angle brackets (use '> >')
vector<vector<int>> a(3, vector<int>(3));
^~
> >
test.cpp:12:15: error: non-aggregate type 'vector<int>' cannot be initialized with an initializer list
vector<int> b = {1, 2, 3, 4, 5};
^ ~~~~~~~~~~~~~~~
test.cpp:22:12: warning: range-based for loop is a C++11 extension [-Wc++11-extensions]
for(int x: b)cout<<x<<",";cout<<endl;
^
1 warning and 2 errors generated.
のエラーが出る。
これを解消するためにはc++11以上にするために-std=c++11オプションをつける。（参考：処理系 - cpprefjp C++日本語リファレンス）
$ make ./test c++ -I .../@AtCoder -std=c++11 test.cpp -o test
さらに、std::gcdやstd::lcmを使うためには-std=c++17オプションを使う。
