P1516 青蛙的约会
传送门
好吧,这是一道裸的拓欧,我也不知道为什么要写这篇博客qwq~~~~
下面开始分析:
我们设总共跳T次可以相遇:
则 A坐标:X+MT; B坐标:Y+NT
那么可以得出:
相遇的充要条件为:(X+MT)-(Y+NT)=PL //P是整数,PL是纬线长度的P倍
变形为:(N-M)* T + L * P=X-Y//T为所求
如果变形成那样还没看出来,那么变成这样总能看出来了吧:(M-N)* T$\equiv$ ≡ (Y-X)(mod L)(注意这个地方有变号,即N-M被我设作M-N,为的是让等式右边冠正号)
没错,它就是个一次同余方程,而我们要做的就是求出它的最小正整数解qwq(特别注意,是正整数,这里有个小坑,后面会讲)
那这就简单了,我们可以通过扩展欧几里德算法求出一组特解,然后对于这组特解,我们再推导出最小解来。
直接套上求最小值代码即可:
x1=(x*(a/d)+l/d)%(l/d);//计算第一个解
cout<<(x1+(l/d))%(l/d);
拓展欧几里得算法应该再熟悉不过了吧
int exgcd(long long a,long long b,long long &x, long long &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
d=exgcd(b,a%b,x,y);
long long t=x;
x=y;
y=t-a/b*y;
return d;
}
然后就信心满满的交上去了,结果发现只获得了70分,怎么回事?
因为gcd只对非负整数有意义,所以如果a<0等式两边要同时取负。
ll a=x-y;
ll b=n-m;
if(b<0)
{
b=-b;
a=-a;
}
最后放上我的AC代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll m,n,x,y,l;
ll d;
int exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
d=exgcd(b,a%b,x,y);
ll temp=x;
x=y;
y=temp-a/b*y;
return d;
}
int main()
{
cin>>x>>y>>m>>n>>l;
ll a=x-y;
ll b=n-m;
if(b<0)
{
b=-b;
a=-a;
}
exgcd(b,l,x,y);
if(a%d)
printf("Impossible");
else
{
int x1=(x*(a/d)+(l/d))%(l/d);//计算第一个解
printf("%d ",(x1+(l/d))%(l/d));
}
return 0;
}
总之,虽然是裸的exgcd题,但是很容易被细节实现坑到,尤其是求最小非负整数解和处理负数的地方。
完结撒花~~~~