扩展欧几里得算法

100s+35t=gcd(100,35)

100和35最大公约数5

gcd(100,35)=5

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

int extgcd(int c, int d, int&x, int&y)
{
    int g = c;
    if(d)
    {
       g = extgcd(d, c % d, y, x);
       y -= (c / d) * x;
    }
    else x = 1, y = 0;
    return g;
}

int main()
{
    int x,y,a,b;
    a=100,b=35;
    extgcd(a,b,x,y);
    cout<<x<<" "<<y;
}