C++ の std::gcd 関数
-
C++ で
std::gcd
関数を使用して 2つの整数の最大公約数を計算する -
C++ で
std::lcm
関数を使用して 2つの整数の最小公倍数を計算する -
C++ で
std::midpoint
関数を使用して 2つの数値の中点を計算する
この記事では、C++ の STL 数値ライブラリから std::gcd
およびその他の便利な数学関数を利用する方法について説明します。
C++ で std::gcd
関数を使用して 2つの整数の最大公約数を計算する
STL は、<algorithm>
ヘッダーを使用して複数のアルゴリズムを提供しますが、強力な数学関数も提供します。その一部は数値アルゴリズムと見なすことができます。これらの関数は、ヘッダー-numeric
を使用して提供されます。
2つの整数の最大公約数を計算する std::gcd
関数について説明します。最大公約数は、指定された各整数を除算する最大の正の整数です。
std::gcd
は 2つの整数値(m
と n
)を取り、|m|
と|n|
の最大公約数を返します。m
と n
の両方がたまたまゼロの場合、関数もゼロを返します。次のサンプルコードは、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