扩展欧几里得（求解方程 ax+by=gcd(a,b)）　　

　　1>当 b=0时：ax+by=a 故而 x=1,y=0

　　2>当 b≠0时：因为gcd(a,b)=gcd(b,a%b)
　　　　　　    而 bx′+(a%b)y′=gcd(b,a%b)
　　　　　　　     bx′+(a−⌊a/b⌋∗b)y′=gcd(b,a%b)
　　　　　　　     ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)=gcd(a,b)
　　　　　     故而x=y′,y=x′−⌊a/b⌋∗y′

　　因此可以采取递归算法先求出下一层的x′和y′再利用上述公式回代即可

#include<bits/stdc++.h>
using namespace std;
int n;
int x, y;
inline int exgcd(int a,int b)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    else
    {
        int gcd=exgcd(b,a%b);
        int z=x;
        x=y;
        y=z-a/b*y;
        return gcd;
    }
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    exgcd(a,b);
    printf("%d %d\n",x,y);
    return 0;
}

扩展欧几里得算法

扩展欧几里得（求解方程 ax+by=gcd(a,b)）

推荐阅读