Stein算法
前言
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;
}
else
if (n % 2 == 0)
n /= 2;
else
if (m % 2 == 0)
m /= 2;
else
if (n > m)
n -= m;
else
m -= 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;
}原文地址：https://blog.csdn.net/NOIP1ding_c/article/details/145139813
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！