2026牛客寒假算法基础集训营4 D题 东风谷早苗与博丽灵梦 前置知识 数论裴蜀定理 exgcd 龟速乘(防爆long long 首先我们来观察一下这道题是两个人相遇求最短时间,那么写成方程就是aX+sY=x的问题 这里总路程是x,首先我们肯定是要能够构造出一个解的,根据裴蜀定理,我们可以知道上面的二元一次方程要有整数解的话,x%gcd(a,s)=0,否则就不能构造出来两个整数解,我们先根据这个进行第一步判断同时求出ax0+sy0=exgcd(a,s) 中的x0和y0 那么回过来看问题我们实际上想要求的是aX+sY=x 那么我们对上面的公式变形,记g=exgcd(a,s) ** 即变为 ax0...