匯東網


gcd 函數

[編輯] [转简体]
|
作者:huidong | 分類:【算法】雜項
[ 3 瀏覽 0 評論 0 贊 0 踩 ]

概要
求解最大公因數

正文

輾轉相除法

int gcd(int m, int n)
{
    if (!m || !n)
        return 1;

    // 準備輾轉相除,首先使 a >= b,r 記錄餘數
    int a = m, b = n, r = 0;
    if (a < b)
        a ^= b ^= a ^= b;
    do
    {
        r = a % b;
        a = b;
        b = r;
    } while (r != 0);

    return a;
}

m * n == 0 時返回 1。

[ 0] [ 0]


 評論區  0 條評論

+ 添加評論