gcd, lcm, exgcd

欧几里得—最大公约数

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

1
2
3
4
5
6
int gcd(int a, int b)
{
    if(b == 0)
        return a;
    return gcd(b, a % )b;
}

一波应用：线段上格点个数—-挑战编程—-欧几里得

algorithm库的std::_gcd函数

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int a = 8;
    int b = 12;
    cout <<__gcd(a, b); //两个'_'
    return 0;
}
//out：4   //g++-4.8

最小公倍数(LCM)和最大公约数(GCD)

lcm(a, b) = (a*b)/gcd(a,b)

扩展欧几里得

基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

当 gcd （ a ， b ）= d 时，求绝对值和最小的 x ， y 使得 x a + y b = d 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//此算法即可求出gcd(a,b)，也可求出x和y。
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int r=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return r;
}