辗转相除法求最大公约数_辗转法求最大公约数

辗转相除法求最大公约数

辗转相除法也被称为欧几里得算法，是求两个整数的最大公约数（GCD）的一种常用方法。

辗转相除法的原理是基于两个整数的最大公约数与它们的余数的最大公约数相等的性质。具体步骤如下：

用较大的数除以较小的数，得到一个商和余数。
如果余数为0，则较小的数即为最大公约数。
如果余数不为0，则用较小的数除以余数，再得到一个商和余数。
不断重复上一步骤，直到余数为0为止。此时，最后一个非0的余数即为两个数的最大公约数。
例如，要求24和36的最大公约数，步骤如下：

36 ÷ 24 = 1…12，余数为12。
24 ÷ 12 = 2…0，余数为0。
因为余数为0，所以24和36的最大公约数为12。

欧几里得算法的时间复杂度为 O(log n)，其中 n 为两个数的较大值，因此在实际应用中具有很高的效率。
下面是使用欧几里得算法（辗转相除法）求两个数的最大公约数的 C++ 代码示例：

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

int main() {
    int a, b;
    cout << "请输入两个整数：" << endl;
    cin >> a >> b;
    cout << "它们的最大公约数为：" << gcd(a, b) << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

代码中的 gcd 函数实现了欧几里得算法，当其中一个数为 0 时，另一个数即为最大公约数，否则继续递归求解两数的余数和较小数的最大公约数。主函数中读入两个数，调用 gcd 函数计算它们的最大公约数并输出。

蓝桥杯真题：

//核心：GCD(F[2020],F[520])=F[GCD(2020,520)]

#include <iostream>
using namespace std;

int GCD(int a,int b)
{
  if(a%b!=0)
    return GCD(b,a%b);
  else
    return b;
}

int main()
{
  int f[2020];
  f[1]=1;
  f[2]=1;

  int i;
  for(i=3;i<=GCD(2020,520);i++)
    f[i]=f[i-1]+f[i-2];

  cout<<f[i-1];
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26