DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Lattice Points on a Segment

Back to problem

Editorial

Let dx=∣x2−x1∣d_x=|x_2-x_1|dx​=∣x2​−x1​∣, dy=∣y2−y1∣d_y=|y_2-y_1|dy​=∣y2​−y1​, and g=gcd⁡(dx,dy)>0g=\gcd(d_x,d_y)>0g=gcd(dx​,dy​)>0. Dividing the direction vector by ggg gives a primitive integer vector. The lattice points on the segment are exactly A+k(B−A)/gA+k(B-A)/gA+k(B−A)/g for integers 0≤k≤g0\le k\le g0≤k≤g. Excluding both endpoints leaves g−1g-1g−1 points. The formula also covers horizontal and vertical segments.

Subtask 1: enumerate integer x-coordinates strictly between the endpoints and test divisibility of (x−x1)(y2−y1)(x-x_1)(y_2-y_1)(x−x1​)(y2​−y by . Handle vertical segments directly. This takes time per case, at most about checks overall.

Subtask 2: compute the gcd with the Euclidean algorithm. Total time is O(Tlog⁡(2⋅109))O(T\log(2\cdot10^9))O(Tlog(2⋅109)) with O(1)O(1)O(1) auxiliary space.

Coordinate differences are at most 2⋅1092\cdot10^92⋅109, the answer is at most 1 999 999 9991\,999\,999\,9991999999999, and the naive product has magnitude at most 4⋅10184\cdot10^{18}4⋅10. Signed 64-bit integers suffice.

∣
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