BZOJ1477 青蛙的约会

青蛙的约会

一看这道题就是同余。然后就开始推方程qwq

[x+mkequiv y+nkpmod L ]

[x+mk-(y+nk)=Lz ]

[(m-n)k+Lz=y-x ]

因为(m-n)、(L)、(y-x)都是已知的，所以这就是一个扩欧的模型。

扩欧就不说了，可以看这篇文章

总体来说，如果你看懂了扩欧，这倒题应该不难，不过细节蛮多的。

1. 不能乱用abs()，考虑好再用。

2. 千万不要变量重名，这导致了我20min的题做了2h。

3. 注意取模时的判负，这是（我认为的）难点

4. 开long long ! 开long long ! 开long long !

……应该就这些了。

Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;

ll x_0,y_0,m,n,L;
ll g,x,y,ans;
ll a,b,c,mod;

inline void readx(ll &x)
{
	x=0;
	int s=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			s=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	x*=s;
}

inline ll gcd(ll a,ll b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}

inline void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b) {x=1;y=0;return;}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}

int main()
{
	readx(x_0);readx(y_0);
	readx(m);readx(n);readx(L);
	a=m-n,b=L,c=y_0-x_0;
	g=gcd(a,b);
	mod=abs(L/g);
	if(c%g)
	{
		printf("Impossible
");
		return 0;
	}
	exgcd(a,b,x,y);
	ans=(x*(c/g)%mod+mod)%mod;
	printf("%lld
",ans);
	return 0;
}