AtCoder Grand Contest 026

最近、競プロ始めたのでメモ。

B問題でgcdを使う部分がわからなくて理由を考えたのでメモ
あってるかどうかはわかりません。

$ g=GCD(B,D) $とする。$ B=gb, D=gd $とする時、$b,d$は互いに素。すると、
$ m=0,1,\cdots,b-1$に対して、$ dm\   \mbox{mod} \  b $は$0,1,\cdots, b-1$になる。この理由は以下の通りに考えることができる。

理由

背理法を用いる。もし、$0,1,\cdots, b-1$にならないとすると、値がかぶるので、
$$ dm_1\   \mbox{mod} \  b =x $$
$$ dm_2\   \mbox{mod} \  b =x $$
$ m_1 \neq m_2 $なので、$$ d(m_1-m_2)=0  \   \mbox{mod} \  b $$
$ (m_1-m_2) $は0より大きくb未満なので、互いに素に矛盾。
よって示せる。

一度アルゴリズムとかを真面目に勉強しないときつそうです
就活までに1600超え目指したいですが、まずは9月に1200超え目指します。