codeforce 7C &&拓展欧几里得 详解

比如说  ax+by=gcd（a，b）

假设  excgcd（int a，int  b，int&x，int&y）是求解这个方程的函数

其返回值是gcd（a，b）（ps： a和b的最大公因子）

假设我们已经求得了b*x1+（a%b）*y1=gcd（a，b）；

x1 ，y1即为其解

又有  a%b=a-(a/b)*b;

带入得

a*y1+b*(x1-(a/b))=gcd(a,b);

而当 b=0时有

a*1+b*0=a=gcd(a,b);

解为......

x=y1,y=y-(a/b)*x;

程序如下；

int  gcd(int n,int  m,ll& x,ll& y){
   int  d=n;
   if(m!=0){
    d=gcd(m,n%m,y,x);
    y-=n/m*x;
   }
   else {
    x=1,y=0;
   }
   return d;
}

比较经典的问题有青蛙约会等

今天是做到一道CF题，

7c   LIne

#include <cstdio>
#include <cstring>
typedef long long ll;
int  a,b,c;
ll x,y;
int  gcd(int n,int  m,ll& x,ll& y){
   int  d=n;
   if(m!=0){
    d=gcd(m,n%m,y,x);
    y-=n/m*x;
   }
   else {
    x=1,y=0;
   }
   return d;
}
int main(){
    scanf("%d%d%d",&a,&b,&c);
    int h=gcd(a,b,x,y);
    if(c%h) printf("-1\n");
    else    printf("%I64d %I64d\n",-x*(c/h),-y*(c/h));
}

codeforce 7C &&拓展欧几里得 详解

原文：http://blog.csdn.net/u013076044/article/details/39031535