令 dx=∣x2−x1∣、dy=∣y2−y1、g=gcd(dx,dy)>0。将方向向量除以 g 后得到分量互质的整数向量。因此线段上的格点恰为 A+k(B−A)/g,其中 k 为满足 0≤k≤g 的整数。去掉两端点后,答案为 g−1。水平和竖直线段也适用。
子任务1:枚举两端点之间的整数 x 坐标,判断 (x−x1)(y2−y 能否被 整除。竖直线段直接计算。每例耗时 ,总计至多约 次检查。
子任务2:用欧几里得算法求最大公约数。总时间复杂度为 O(Tlog(2⋅109)),额外空间为 O(1)。
坐标差至多为 2⋅109,答案至多为 1999999999,朴素解法中乘积的绝对值不超过 4⋅10,有符号64位整数足够。