Atcoder ABC60[B]
小問をもうひとつ投稿。
解説
整数問題で大学受験を思い出させるような問題。ビデオ解説では全探索で解くやり方を説明していたが、最後に触れられていた’制約が厳しくなっても解ける方法’で自分は解いていたのでちょっと嬉しかった。
- 式の展開
まず(7,5,1)の場合を考える。条件より、
7n = 5m +1
⇔ 7n - 5m = 1 ...(1)
このとき、たとえば(n,m) = (3,4)で(1)式は成り立つ。
- 整数の基本定理
ここで整数の基本定理を持ちだす。すなわち整数の式、
aX + bY = cについて、(a,b)が互いに素なら、任意の整数cで式が成り立つ（！）。
具体的には7n - 5m=1のみならず、右辺が2でも10000でもこの式を満たすような整数(n,m)の組が存在する。詳細についてはgoogle検索。
- ngcd (n個の整数の最大公約数)
喜び勇んで(a,b)が互いに素かどうかを判定するプログラムを書いて投稿するとあっさり落ちる（落ちた）。よくよく考えると、式全体が簡約化できる場合を処理する必要がある。たとえば例４は(a,b)は互いに素ではないが、式全体を２で割ることができる。結局、a,b,cの最大公約数を求めて式を簡単にしなければならない。
ngcd関数の書き方は定番があって、それは解答の通りになる。
ngcdで処理したあと、満を持して(a,b)の互いに素判定に乗り出せばめでたくACとなる。
- AtCoderはじめました
厳密に言えばこの間のグランドコンテストにも出たので二回目だったが、そのときはノー勉だったので全然解けなかった。今回はABCだけにそれなりに解くことができた。どんどんレーティングを上げていきたい。正しいレーティング計算には１０回参加しろと書いてあるけれど、それってあと２，３ヶ月はまともな成績がつかないってことか。気の長い話になる。その間に実力を養成しておきたい。
