#C240924F. 青蛙的约会
标签（Label）
exgcd
数学
模板
网址（Website）
练习题：#C240924B. 吃药
扩展欧几里得定义（Definition）
$\qquad$这个真的很重要！！！
$\qquad$对于函数 $\verb!d = exgcd(a,b,x,y)!$ ，得到的 $d$ 是 $a$ 和 $b$ 的 $gcd$ ， $x$ 和 $y$ 是满足 $ax+by\equiv gcd(a,b)$ 的一组解，可以理解为再跳 $x$ 个 $a$ 和再跳 $y$ 个 $b$ 他们加起来的和同余 $gcd(a,b)$ 。
题解（Solution）
此题其实就是用扩展欧几里德算法求解不定方程。
设跳跃 $s$ 步后两青蛙相遇，则有：
原坐标为 $x$ 的青蛙在相遇处的坐标值为：$x + m \cdot s$
原坐标为 $y$ 的青蛙在相遇处的坐标值为：$y + n \cdot s$
两个青蛙如果在第一圈相遇，相遇处坐标相同，则坐标差为 $0$；如果在第二圈相遇，则相遇坐标差为 $1 \cdot L$，……，所以相遇处坐标差为 $k \cdot L$（$k = 0, 1, 2, \ldots$）。
则必满足以下等式：$(x + m \cdot s) - (y + n \cdot s) = k \cdot L \quad (k = 0, 1, 2, \ldots)$
稍微变一下形得：$(n - m) \cdot s + k \cdot L = x - y$
令 $a = n - m, b = L, c = x - y$ ，则有：$a \cdot s + b \cdot k = c$
只要上式存在关于 $s$ 和 $k$ 的整数解，则两青蛙能相遇，否则不能。
代码（Code）
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int g(int a,int b,int &x,int &y){
if(b==0){
x = 1, y = 0;
return a;
}
int d = exgcd(b,a%b,y,x);
y -= a / b * x;
return d;
}
signed main(){
ios::sync_with_stdio(false);
int x,y,n,m,X,Y,L,d,r;
cin>>x>>y>>m>>n>>L;
d=g(n-m,L,X,Y);r=L/d;
if((x-y)%d) cout<<"Impossible\n";
else cout<<((x-y)/d*X%r+r)%r<<'\n';
}
