虽然过了,但还是不明白为啥会错,求高人点拨
查看原帖
虽然过了,但还是不明白为啥会错,求高人点拨
22240
卢浙浩楼主2021/4/30 01:38

我是考虑到本题相当于 青蛙A以 v=(mn)v = (m-n)%l 的相对速度,追前方 x=(yx)x = (y-x)%l 处的青蛙B(这样可以避免对负数进行讨论)

这样,问题就转化成了求解vt+lk=xvt+lk=x,即解同余方程vtx(mod l)vt\equiv x\quad (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了。但我还是不明白原来为啥会错。关键的同余方程vtx(mod l)vt\equiv x\quad (mod\ l)中,v,x,l同时乘一个整数,结果应该不变啊

2021/4/30 01:38
加载中...