我是考虑到本题相当于 青蛙A以 v=(m−n) 的相对速度,追前方 x=(y−x) 处的青蛙B(这样可以避免对负数进行讨论)
这样,问题就转化成了求解vt+lk=x,即解同余方程vt≡x(mod l)
原先的问题代码:
def gcd(a,b):
if not b:
return a
return gcd(b,a%b)
def exgcd(a,b):
if not b:
return 1,0
x,y=exgcd(b,a%b)
return y,x-a//b*y
def inv(n,p):
return exgcd(n,p)[0]%p
x,y,m,n,l=[int(x)for x in input().split()]
v=(m-n)%l
x=(y-x)%l
if x%gcd(v,l)==0:
print((x*inv(v,l))%l)
else:
print('Impossible')
问题处在第4组数据,输入数据都是2的倍数,此时输出结果也是答案的两倍。于是我在if前面加上了这4行:
t=gcd(gcd(x,v),l)
x//=t
v//=t
l//=t
于是就AC了。但我还是不明白原来为啥会错。关键的同余方程vt≡x(mod l)中,v,x,l同时乘一个整数,结果应该不变啊