欧几里得

求最大公约数（最大公因子　GCD）

• 质因数分解法

  例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）=12。

• 辗转相除法

  gcd(a,b) = gcd(b,a mod b)

1
2
3
4

int gcd(int a,int b)
{
	return b == 0?a:gcd(b,a%b);
}

• 迭代形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
using namespace std;

int gcd(int a,int b)
{
   int r;
   while(b!=0)
   {
      r = b;
      b = a%b;
      a = r;

   }
   return a;
}
int main()
{
   int a,b;
   cin >> a >> b;
   cout <<  gcd(a,b) << endl;
   return 0;
}

• C++内置函数法

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  #include <iostream> #include <algorithm> using namespace std; int gcd(int a,int b) { return std::__gcd(a,b); } int main(){ int a=24,b=60; int ans = gcd(a,b); cout << ans <<endl; return 0; }

最小公倍数（LCM）

把几个数先分别分解质因数，再把各数中的全部公有的质因数和独有的质因数提取出来连乘，所得的积就是这几个数的最小公倍数

求6和15的LCM。先分解质因数，得6=2×3，15=3×5，2×3×5=30，30是6和15的公倍数中最小的一个，所以[6，15]=30。

1
2
3
4

int lcm(int a,int b)
{
    return a/gcd(a,b) * b;
}

扩展欧几里得算法

方程符合ax + by = n，则gcd(a,b)能整除n,可用扩展欧几里得算法求（x0,y0)

1
2
3
4
5
6
7
8
9
10
11
12
13

void exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
    {
        x = 1;
        y = 0;
        return ;
    }
    exgcd(b,a%b,x,y);
    int tmp = x;
    x = y;
    y = tmp - (a-b)*y;
}

• ← Previous Post
• Next Post →