DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

线段上的格点

返回题目

题解

令 dx=∣x2−x1∣d_x=|x_2-x_1|dx​=∣x2​−x1​∣、dy=∣y2−y1∣d_y=|y_2-y_1|dy​=∣y2​−y1​、g=gcd⁡(dx,dy)>0g=\gcd(d_x,d_y)>0g=gcd(dx​,dy​)>0。将方向向量除以 ggg 后得到分量互质的整数向量。因此线段上的格点恰为 A+k(B−A)/gA+k(B-A)/gA+k(B−A)/g,其中 kkk 为满足 0≤k≤g0\le k\le g0≤k≤g 的整数。去掉两端点后,答案为 g−1g-1g−1。水平和竖直线段也适用。

子任务1:枚举两端点之间的整数 x 坐标,判断 (x−x1)(y2−y1)(x-x_1)(y_2-y_1)(x−x1​)(y2​−y 能否被 整除。竖直线段直接计算。每例耗时 ,总计至多约 次检查。

子任务2:用欧几里得算法求最大公约数。总时间复杂度为 O(Tlog⁡(2⋅109))O(T\log(2\cdot10^9))O(Tlog(2⋅109)),额外空间为 O(1)O(1)O(1)。

坐标差至多为 2⋅1092\cdot10^92⋅109,答案至多为 1 999 999 9991\,999\,999\,9991999999999,朴素解法中乘积的绝对值不超过 4⋅10184\cdot10^{18}4⋅10,有符号64位整数足够。

∣
1
​
)
x2−x1x_2-x_1x2​−x1​
O(∣x2−x1∣+1)O(|x_2-x_1|+1)O(∣x2​−x1​∣+1)
400 000400\,000400000
18