難易度7

f:id:poyopoyoyon:20180323013845p:plain

難易度7を埋めました。→ AOJ/AtCoder-JOI

埋めたといいつつ、100%ではないです。（1つは提出してもIEになるので）

HTTF 2018 qual

9891030405点

本番の後、この記事（競プロ解法紹介～レベル別マラソンの戦い方～）を参考にして解き直したら9990441025点になりました*1

問題

格子点2点を結ぶ線分上にある格子点は（端点を含めて）いくつありますか

答え

$gcd(|x_1-x_2|, |y_1-y_2|)+1$ 個です

原点(0, 0)と(a, b)を結ぶ線分を考えていいでしょう（a≧0, b≧0, a,bは整数）

もとの問題はむずかしすぎるので、解ける問題を解きます。a, bが互いに素だとします。a=a', b=b', a'⊥b'です。このとき、あきらかに求める格子点の数は原点と(a', b')の2つです。

a, bが互いに素ではないとします。g=gcd(a, b)としてa=ga', b=gb' (a'⊥b') とおきます。すると求める格子点は(0, 0), (a', b'), (2a', 2b'), ..., (ga', gb')のg+1個です。

これが解けなかったので書きました。