首页 > 东风谷早苗与博丽灵梦
开通博客写题解
头像 呵后有呵
发表于 2026-02-10 01:48:11
2026牛客寒假算法基础集训营4 D题 东风谷早苗与博丽灵梦 前置知识 数论裴蜀定理 exgcd 龟速乘（防爆long long 首先我们来观察一下这道题是两个人相遇求最短时间，那么写成方程就是aX+sY=x的问题 这里总路程是x，首先我们肯定是要能够构造出一个解的，根据裴蜀定理，我们可以知道上面的 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 cslg0922242zz
发表于 2026-02-20 16:38:11
题意: 求的最小非负整数解 知识点: 裴蜀定理，扩展欧几里得算法 思路: 我们先简化符号为ax+by=L，根据裴蜀定理得知ax+by=gcd(a,b)一定有x,y不全为0的整数解 所以如果L不是gcd(a,b)的整数倍则一定无解。 接着根据辗转相除法我们得知gcd(a,b)=gcd(b,a%b) 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”