おはやし日記

特にテーマ無しの日記。

cとc++で最大公約数、最小公倍数を求める

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)$$ 最大公約数と最小公倍数の積の性質の2通りの証明 | 高校数学の美しい物語より改変

つまり、$$\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を求める関数は…………gcdlcmに書き換えるだけですが、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_arrlcm_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)で使えます。

おしまい。

参考


  • 個人的メモ

vscodeでのc++

$ 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オプションを使う。

プライバシーポリシー ・お問い合わせはこちら