C++ の std::gcd 関数

胡金庫 2023年10月12日
  1. C++ で std::gcd 関数を使用して 2つの整数の最大公約数を計算する
  2. C++ で std::lcm 関数を使用して 2つの整数の最小公倍数を計算する
  3. C++ で std::midpoint 関数を使用して 2つの数値の中点を計算する
C++ の std::gcd 関数

この記事では、C++ の STL 数値ライブラリから std::gcd およびその他の便利な数学関数を利用する方法について説明します。

C++ で std::gcd 関数を使用して 2つの整数の最大公約数を計算する

STL は、<algorithm> ヘッダーを使用して複数のアルゴリズムを提供しますが、強力な数学関数も提供します。その一部は数値アルゴリズムと見なすことができます。これらの関数は、ヘッダー-numeric を使用して提供されます。

2つの整数の最大公約数を計算する std::gcd 関数について説明します。最大公約数は、指定された各整数を除算する最大の正の整数です。

std::gcd は 2つの整数値(mn)を取り、|m||n|の最大公約数を返します。mn の両方がたまたまゼロの場合、関数もゼロを返します。次のサンプルコードは、std::gcd の基本的な使用法を示し、対応する結果をコンソールに出力します。

#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

using std::cout;
using std::endl;
using std::setw;
using std::vector;

int main() {
  std::vector<std::pair<int, int>> vec = {
      {12125, 1235}, {124, 1122}, {-1235, 321}, {12, 144}};

  for (const auto &item : vec) {
    cout << "Greatest common divisor of " << setw(5) << item.first << " and "
         << setw(5) << item.second << " is "
         << std::gcd(item.first, item.second) << endl;
  }

  return EXIT_SUCCESS;
}

出力:

Greatest common divisor of 12125 and  1235 is 5
Greatest common divisor of   124 and  1122 is 2
Greatest common divisor of -1235 and   321 is 1
Greatest common divisor of    12 and   144 is 1

C++ で std::lcm 関数を使用して 2つの整数の最小公倍数を計算する

数値ライブラリで提供されるもう 1つの同様の関数は、std::lcm です。これは、2つの整数の最小公倍数を計算します。この関数は、std:gcd と同様の 2つの整数を受け入れ、|m|の最小公倍数を返します。および|n| (引数を示します)。

これらの関数の両方に constexpr 指定子があることに注意してください。これは、定数式で使用される可能性があり、関数がインライン分類を取得することを意味します。

#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

using std::cout;
using std::endl;
using std::setw;
using std::vector;

int main() {
  std::vector<std::pair<int, int>> vec = {
      {12125, 1235}, {124, 1122}, {-1235, 321}, {12, 144}};

  for (const auto &item : vec) {
    cout << "Least common multiple of " << setw(5) << item.first << " and "
         << setw(5) << item.second << " is "
         << std::lcm(item.first, item.second) << endl;
  }

  return EXIT_SUCCESS;
}

出力:

Least common multiple of 12125 and  1235 is 2994875
Least common multiple of   124 and  1122 is 69564
Least common multiple of -1235 and   321 is 396435
Least common multiple of    12 and   144 is 144

C++ で std::midpoint 関数を使用して 2つの数値の中点を計算する

std::midpoint は、ユーザーがオーバーフローを心配することなく、指定された 2つの数値の半分を計算するための機能的な関数です。つまり、合計が 64 ビット整数の上限よりも大きい 2つの大きな整数の半分を計算しようとすると、オーバーフローが発生し、結果が不正確になります。

例として、次のコードスニペットは、2つの整数の中点を見つけようとします。一方は、uint64_t に格納できる最大数と同じで、もう一方は 10 未満です。通常の算術演算子を使用した計算では間違った数値が生成されますが、std::midpoint は正しい結果を返すことに注意してください。

ただし、この関数は C++ 20 標準以降の言語の一部であり、古いバージョンでは使用できない場合があることに注意してください。std::midpoint はポインタ値でも機能しますが、指定されたポインタは同じ配列の要素である必要があります。それ以外の場合、動作は定義されていません。

#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

using std::cout;
using std::endl;
using std::setw;
using std::vector;

int main() {
  uint64_t a = std::numeric_limits<uint64_t>::max();
  uint64_t b = std::numeric_limits<uint64_t>::max() - 10;

  cout << "a: " << a << '\n'
       << "b: " << b << '\n'
       << "Incorrect: " << setw(20) << (a + b) / 2 << '\n'
       << "Correct  : " << setw(20) << std::midpoint(a, b) << endl;

  return EXIT_SUCCESS;
}

出力:

a: 18446744073709551615
b: 18446744073709551605
Incorrect:  9223372036854775802
Correct  : 18446744073709551610
著者: 胡金庫
胡金庫 avatar 胡金庫 avatar

DelftStack.comの創設者です。Jinku はロボティクスと自動車産業で8年以上働いています。自動テスト、リモートサーバーからのデータ収集、耐久テストからのレポート作成が必要となったとき、彼はコーディングスキルを磨きました。彼は電気/電子工学のバックグラウンドを持っていますが、組み込みエレクトロニクス、組み込みプログラミング、フロントエンド/バックエンドプログラミングへの関心を広げています。

LinkedIn Facebook