前言
Stein算法是一种计算两个数最大公约数的算法,旨在改进在处理大整数时效率低下的问题。该算法通过减法和位移操作替代除法,提高了计算速度,尤其适用于硬件实现。
思路
具体步骤如下:
- 初始化:如果A=0,B是最大公约数,算法结束;如果B=0,A是最大公约数,算法结束。
- 迭代过程:
- 如果A和B都是偶数,则同时除以2,并记录除去的因子2的乘积。
- 如果一个是偶数一个是奇数,则将偶数除以2,奇数保持不变。
- 如果A和B都是奇数,则用较大的数减去较小的数,然后取差与较小的数继续操作。
- 结束条件:当A和B相等时,停止迭代。此时,记录的2的乘积与A(或B)的最大公约数的乘积就是所求的最大公约数。
代码解决
#include <iostream>
using namespace std;
long long Highest_Common_Factor;
static void Stein(int a, int b) {long long n = a, m = b, c = 1;while (n == m)if (n % 2 == 0 && m % 2 == 0) {n /= 2;m /= 2;c *= 2;}elseif (n % 2 == 0)n /= 2;elseif (m % 2 == 0)m /= 2;elseif (n > m)n -= m;elsem -= n;Highest_Common_Factor = m * c;
}
int main() {int a, b;cin >> a >> b;Stein(a, b);cout << a << "和" << b << "的最大公因数是:" << Highest_Common_Factor << endl;return 0;
}