POJ 1061扩展欧几里得

扩展欧几里得的模板题，需要注意的是为了得到一个最小正数解我们要使ax+by=c中的a,b都是正数

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> #include<cmath> #include<ctime> #include<climits> #include<queue> #include<vector> #include<set> #include<map> using namespace std;typedef long long ll; const int INF=0x3f3f3f3f; const int MAXN=1e5+5;ll x,y,m,n,L;void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y) {if(!b){d=a; x=1; y=0;}else{ex_gcd(b,a%b,d,y,x); y-=(a/b)*x;} }int main() {while(~scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L)){ll k,t,A,B,C,d;if(m>=n){A=m-n; B=L; C=y-x;}else{A=n-m; B=L; C=x-y;}ex_gcd(A,B,d,k,t);if(C%d){printf("Impossible\n");continue;}k=C/d*k%(L/d);if(k<0) k+=(L/d);printf("%lld\n",k);}return 0; }

总结

以上是生活随笔为你收集整理的POJ 1061扩展欧几里得的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。