介绍

欧几里得算法又名辗转相除法，是用于快速求解最大公约数的算法

原理

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数

实现

我们可以使用c++ 中<algorithm>头文件中的__gcd(a, b)函数来求a，b的最大公约数，也可以自己写一个程序来实现它
c语言实现代码</algorithm>

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

练习题

UVA - 11827

#include<iostream>
#include<string>
#include<stdio.h>
#include<sstream>
#include<algorithm>
using namespace std;

const int maxn = 100 + 10;
int a[maxn];

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

int main()
{
    int T;
    cin >> T; getchar();
    string s;
    while(getline(cin, s))
    {
        int Max = 0;
        stringstream ss(s);
        int n = 0;
        while(ss >> a[n]) n++;
        for(int i = 0; i < n ; i++)
            for(int j = i + 1; j < n; j++)
            {
                Max = max(Max, gcd(a[i],a[j]));
            }
        printf("%d\n",Max);
    }
    return 0;
}

ZOJ - 3609

#include<stdio.h>
#include<algorithm>
using namespace std;

typedef long long LL;

void gcd(LL a, LL b, LL &d, LL &x, LL &y)
{
    if(!b)
    {
        d = a;
        x = 1;
        y = 0;
    }
    else
    {
        gcd(b,a%b,d,y,x);
        y -= x * (a / b);
    }
}

int main()
{
    LL x,y,d,a,n;
    int T;
    scanf("%d",&T);
    for(int kase = 1; kase <= T; kase++)
    {
        scanf("%lld%lld",&a,&n);
        gcd(a,n,d,x,y);
        if(d != 1) printf("Not Exist\n");
        else
        {
            while(x > n) x -= n;
            while(x <= 0) x += n;
            printf("%lld\n",x);
        }
    }
    return 0;
}