C++ 中的 std::gcd 函式

Jinku Hu 2023年1月30日 2021年10月2日
  1. 使用 std::gcd 函式在 C++ 中計算兩個整數的最大公約數
  2. 在 C++ 中使用 std::lcm 函式來計算兩個整數的最小公約數
  3. 使用 std::midpoint 函式在 C++ 中計算兩個數字的中點
C++ 中的 std::gcd 函式

本文將解釋如何在 C++ 中使用 STL 數值庫中的 std::gcd 和其他有用的數學函式。

使用 std::gcd 函式在 C++ 中計算兩個整數的最大公約數

STL 使用 <algorithm> 頭提供了多種演算法,但它也提供了強大的數學函式,其中一些可以被認為是數值演算法。這些函式是使用標題 - numeric 提供的。

我們將探索計算兩個整數的最大公約數的 std::gcd 函式。最大公約數是將每個給定整數相除的最大正整數。

std::gcd 接受兩個整數值(mn)並返回 |m||n| 的最大公約數。如果 mn 碰巧都為零,則該函式也返回零。下面的示例程式碼演示了 std::gcd 的基本用法,並將相應的結果列印到控制檯。

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

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

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 函式來計算兩個整數的最小公約數

數字庫中提供的另一個類似函式是 std::lcm,它計算兩個整數的最小公倍數。該函式接受兩個類似於 std:gcd 的整數,並返回|m||n|(表示引數)的最小公約數。

請注意,這兩個函式都有 constexpr 指定符,這意味著它們可能用於常量表示式,並且該函式也獲得了 inline 分類。

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

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

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

使用 std::midpoint 函式在 C++ 中計算兩個數字的中點

std::midpoint 是一個功能強大的函式,用於計算兩個給定數字的一半,而使用者無需擔心溢位。即,如果我們嘗試計算兩個大整數的一半,它們的總和大於 64 位整數的上限,那麼我們就會溢位,結果將是錯誤的。

例如,以下程式碼片段試圖找到兩個整數的中點,其中一個與 uint64_t 中可以儲存的最大數相同,另一個小於 10。請注意,使用常用算術運算子的計算會產生錯誤的數字,而 std::midpoint 返回正確的結果。

請注意,此函式自 C++20 標準以來一直是語言的一部分,可能在舊版本中不可用。std::midpoint 也適用於指標值,但給定的指標應該是同一陣列的元素。否則,行為是未定義的。

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

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

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
Author: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn