首页 > itarticle > 扩欧

扩欧

admin 11月 13, 2020 0

已知a，b，求x，y使得ax+by=gcd（a，b）

原理

利用欧几里得递推可得
gcd(a,b)=gcd(b,a%b)
ax+by=bX+(a%b)Y
(b(a/b)+a%b)x+by=bX+(a%b)Y
b((a/b)x+y-X)+(a%b)(x-Y)=0
–>
X=(a/b)x+y,Y=x
以上便递推式

代码


#define LL long long
using namespace std;
LL a,b,x=1,y=0;
void (LL n,LL m){
    if(m==0) return;
    gcd(m,n%m);
    LL p=x;
    x=y;
    y=p-n/m*y;
}
 
int main(){
    ios::sync_with_stdio(false);
    LL a,b; 
    cin>>a>>b;
    gcd(a,b);
    cout<<(x+b)%b;
    return 0;
}