(Relax 数论1.6)POJ 1061 青蛙的约会(扩展的欧几里得公式)

/*
* POJ_1061.cpp
*
* Created on: 2013年11月19日
* Author: Administrator
*/ #include <iostream>
#include <cstdio> using namespace std; typedef long long ll; /**
* 扩展的欧几里得计算d=gcd(a,b)=ax+by的整系数x,y
*/
ll exgcd(ll a,ll b,ll& x ,ll& y){
if(b == 0){
x = 1;
y = 0;
return a;
} ll t = exgcd(b,a%b,y,x);
y -= a/b*x;
return t;
} /**
* 求a、b的最大公约数
*/
ll gcd(ll a,ll b){
if(b == 0){
return a;
} return gcd(b,a%b);
} int main(){
ll x,y,m,n,l;
ll a,b,d,s,k,t;
while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)!=EOF){
a = n-m;
b = l;
d = x - y;
ll r = gcd(a,b);
if(d % r){//这时方程无解
printf("Impossible\n");
continue;
} a /= r;//化简,使得a、b互质
b /= r;
d /= r;
exgcd(a,b,s,k); s = s*d;//求s的最小值
k = k*d;
t = s/b;
s = s - t*b;
if(s < 0){
s += b;
} printf("%lld\n",s);
} return 0;
}
上一篇:帆软报表FineReport数据库连接编码转换


下一篇:vuex 状态管理 通俗理解