题解 P1516 【青蛙的约会】
FlashHu
2018-06-07 10:01:05
很容易想到,如果他们相遇,他们初始的位置坐标之差$x-y$和跳的距离$(n-m)t$(设$t$为跳的次数)之差应该是模纬线长$l$同余的,即$(n-m)t\equiv x-y(\mod l)$
转化一下,不就变成了让我们求一个不定方程$(n-m)t+kl=x-y(k\in \mathbb Z)$中$t$的最小非负整数解么?
设$a=n-m,b=l,c=x-y$,把它转化成我们比较熟悉的一般不定方程的形式$ax+by=c$(此式的$x,y$与题目给的坐标意义不同)
首先,设$g=\gcd(a,b)$我们可以通过扩欧求出$ax_0+by_0=g$中$x_0$的一个解
这时,因为$\frac{ax+by}g$为整数,所以$\frac c g$也必须是整数,否则无解
否则,等式两边同乘$\frac cg$,得$a\frac{cx_0}g+b\frac{cy_0}{g}=c$
那么,$x=\frac{cx_0}g$就是$ax+by=c$中$x$的一个解
如何由一个解得到其它解呢?有一个恒等式$a(x+db)+b(y-da)=c$
在保证$db,da$都是整数的情况下,我们让$d$最小,就可以得到所有的整数解,那么$d=\frac 1g$
如果解出的$x>0$,那么最小非负整数解等于$x\mod\frac b g$;否则等于$x\mod\frac b g+\frac b g$
代码就可以直接写`(x%(b/g)+b/g)%(b/g)`
然后就可以交上去了,发现获得了70分
怎么回事?因为$\gcd$只对非负整数有意义,所以如果$a<0$等式两边要同时取负,$a,c$都要变成相反数;$b$本来就是正数,不用变也不能变。
总之,虽然是裸的exgcd题,但是很容易被细节实现坑到,尤其是求最小非负整数解和处理$a$为负数的地方。
```cpp
#include<cstdio>
#define LL long long
LL x,y,m,n,l,a,b,c,x0,y0,g,tmp;
void exgcd(LL a,LL b){
if(!b){x0=1;g=a;return;}//顺便求gcd
exgcd(b,a%b);
tmp=x0;x0=y0;y0=tmp-a/b*y0;
}
int main(){
scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
a=n-m;b=l;c=x-y;
if(a<0)a=-a,c=-c;//处理a为负数情况
exgcd(a,b);
if(c%g)puts("Impossible");
else printf("%lld\n",(c/g*x0%(b/g)+b/g)%(b/g));//求最小非负整数解
return 0;
}
```