#include<bits/stdc++.h>using namespace std;/*计算不定方程:AX+BY==1的解推导过程：必定存在Ax+By=gcd(A,B)的解x,y--->kwdjz拓展又gcd(A,B)=gcd(B,A%B)--->kwdjz定理（辗转相除法）则必有Bx+(A%B)y=gcd(B,A%B)--->①此时，我们考虑怎么每次把x,y解出一点出来,并且，我们每一次已知的信息量是上一次的A,B,x,y于是，A%B=A-A/B*B由①得:Bx+(A-A/B*B)y=gcd(B,A%B)=>Ay+B(x-A/B*B*y)=gcd(B,A%B)此时，我们令x1=y,y1=x-A/B*y这样是不是得到一个类似于最开始的公式:Ax1+By1=gcd(A,B)而出口就是找到A,B的最大公因数，此时，由于A,B!=0,则必有:x=1,y=0;这样，我们通过在找A,B的一组最大公因数的时候同时找出了不定方程的一组特解，至于通解的话，个人认为要去找一组Ac+Bd=0成立的整数(由于最近才搞这个定理，如有发现错误，望不吝赐教！) */int e_gcd(int A,int B,int a[]) //拓展kwdjz{if(B==0){a[0]=1;a[1]=0;return A;}int ans=e_gcd(B,A%B,a);int t=a[0];a[0]=a[1];a[1]=t-A/B*a[1];return ans;}int main(){int a[2];printf("%dn",e_gcd(97,-127,a));printf("x=%d y=%dn",a[0],a[1]);return 0;}