codeforce 7C 拓展欧几里得 详解

本文主要是介绍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 拓展欧几里得 详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---