poj 1061 青蛙的约会 拓展欧几里得模板

// poj 1061 青蛙的约会 拓展欧几里得模板

// 注意进行exgcd时,保证a,b是正数,最后的答案如果是负数,要加上一个膜

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath> using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
if (b==)
return a;
return gcd(b,a%b); }
ll x,y,m,n,l; ll exgcd(ll a,ll b,ll &x,ll &y){
if ( b == ){
x = ;
y = ;
return a;
}
ll d = exgcd(b,a%b,x,y);
ll temp = x;
x = y;
y = temp - a / b * y;
return d;
} int main(){
//freopen("1.txt","r",stdin);
while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)!=EOF){
ll u = m - n;
ll v = y - x;
if (u < ){
u = -u;
v = -v;
} ll x1,y1;
ll d = exgcd(u,l,x1,y1); if (v % d){
puts("Impossible");
continue;
} ll mod = l / d; x1 = x1 * ( v / d);
printf("%lld\n",(x1%mod + mod)%mod);
}
return ;
}
上一篇:jQuery里面的DOM操作(查找,创建,添加,删除节点)


下一篇:js中json法创建对象(json里面的:相当于js里面的=)