DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

線分上の格子点

問題に戻る

解説

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 で割ると、成分が互いに素な整数ベクトルになる。線分上の格子点は整数 0≤k≤g0\le k\le g0≤k≤g に対する A+k(B−A)/gA+k(B-A)/gA+k(B−A)/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