寒假集训专题四-G.青蛙的约会

g青蛙的约会

题意：两青蛙在环形的轨道上不同位置开始运动，求相遇的时间

思路：

根据题意可知 即求x+mt≡y+nt(mod L)的解

根据同余可化为 L|(x+mt-y-nt)

进一步化为 kL+(n-m)t=x-y

这里k为整数(因为可能是当圈相遇，也可能套圈)，即求t的最小正整数解

注意：gcd仅对正整数生效，并且右边x-y是负数不影响

最后套入扩欧公式

最小正整数解公式

可以这样想 -1%3 下的答案是？2 可以用floor_mod

int  floor_m(int n,int m)
{
	return n-(floor(n/(float)m)*m);
} 

#include
#include
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0) {x=1,y=0;return a;};
	ll d=exgcd(b,a%b,x,y);
	ll z=x; x=y; y=z-a/b*y;
	return d;
}
int main()
{
	ll x,y,m,n,l;
	cin>>x>>y>>m>>n>>l;
	if(m>n) swap(m,n),swap(x,y); 
	ll d=x-y;
	ll z=n-m;
	ll g=gcd(l,z);
	if(z == 0 ||d%g!=0)
	{
		cout<<"Impossible";
		return 0;
	}
	ll a,b;
	ll f=exgcd(l,z,a,b);
	b=(b*d/g%(l/g)+l/g)%(l/g);
	cout<