po

HTTF 2018 qual

問題

HACK TO THE FUTURE 2018予選 - AtCoder

本番の解答

9891030405点

Submission #2104678 - HACK TO THE FUTURE 2018予選

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

f:id:poyopoyoyon:20180219130301p:plainf:id:poyopoyoyon:20180219130618p:plain
左:989...点 右:999...点

続きを読む

格子点とGCD

問題

格子点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個です。




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

Myblog

ドットインストールのRuby on Rails 5入門の言うとおりにしてたらできるやつ↓

https://shrouded-castle-19234.herokuapp.com/

Myblog

続きを読む