扩展欧几里得解二元一次不定方程
两只青蛙，起点分别为x,y ,每次可以跳m,n长度。（同方向跳）在长为 l 的圆表面，最少跳多少次相遇。
设跳k次，则(k*m x) - (k*n y) = p*l 假设前面的多跳 p圈。
变为ax by = c的形式套用扩展欧几里得模版。这里是输出x的最小值。
得到答案 *c/p得 原方程特解之一，以x为例， 如果是非负数 直接%(b/gcd(a,b)) ,负数就先%(b/gcd(a,b)) ，再加%(b/gcd(a,b))
代码语言：javascript复制#include <iostream>
#define ll long long
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y) {
if(!b) {//解方程求 x,y a*x b*y = gcd(a,b)
x=1,y=0;
return a;
}
ll re=exgcd(b,a%b,x,y),tmp=x;
x=y,y=tmp-(a/b)*y;
return re;
}
int main() {
ll x,a,b,y,c,m,n,l,p;
cin>>x>>y>>m>>n>>l;
a = n-m;
b = l;
c = x-y;
//求 ax by = c
p = exgcd(a,b,x,y);// 先求 ax by = gcd(a,b)
if(c%p!=0) {// 无解
printf("Impossiblen");
} else {
x = x*c/p; // 这里输出 x, 解*c/p 为通解
if(x>=0) { //求最小解
x%=b/p;
} else {
x = x%b/p b/p;
}
printf("%lldn",x);
}
return 0;
}
