欧几里得算法

Star_LIcsAy · 2021-10-01 16:56:06 · 个人记录

欧几里得算法的核心是：

我们定义 \gcd(a,b) 为求得 a,b 最大公因数的函数，则有 \gcd(a,b)=\gcd(b,a\%b).

证明：

假设 d 为 a 与 b 的最大公约数，令 a 大于 b，a,b＞0。

则 a 可以表示为 m×d ，b 可表示为 n×d ( m,n＞0)。

我们定义 k 为 m/n 的商，且 k>0.

则有 a\%b=(m-k×n)×d，d 同样也是 a\%b 的因数，所以对结果不产生影响。

当 b=0 的时候，b 当然也算是 a 的倍数(0×d)，这时的 a 就是我们所需要的最大公约数。

例题：P1888 三角函数

• 虽然名字叫三角函数，但其实和三角函数基本没什么关系。

• 我们需要使用欧几里得算法来求得两值的最大公约数，来达到对原分数进行化简的效果。

#include<bits/stdc++.h>
using namespace std;

int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}

int main(){
    int a[5];
    for(int i=1;i<4;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+4);
    int d=gcd(a[1],a[3]);
    a[1]/=d,a[3]/=d;
    printf("%d/%d",a[1],a[3]);
    return 0;
}

• 欧几里得算法的高级写法（三目运算）

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

扩展欧几里得算法

其主要目的是，通过在计算 \gcd(a,b) 时得到的数据，倒推得到不定方程 ax+by=\gcd(a,b) 的通解。

• 例：P1516 青蛙的约会

  T201531 简单不简单

int ex(int a,int b){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int d=ex(b,a%b);
    int temp=x;
    x=y;
    y=temp-a/b*y;
    return d;
}
//最后的x和y就是上述不定方程的解(x有可能为负)