po

難易度7

f:id:poyopoyoyon:20180323013845p:plain

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

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

感想など → https://comprolog.netlify.com/categories/joi/

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




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