yukicoder No.982 Add
$ S:= \{pa+qb|p,q \in \mathbb{Z}_{\geq 0}\}に含まれない非負整数の数を求める。
$ X:=\{pa+qb| 0 \leq p < b, 0\leq q < a\}とする。
$ a,bが互いに素な場合のみを考える。
中国剰余定理よりXの$ 0 \leq s < b, 0 \leq t < aの元は$ \mathbb{Z}/ab\mathbb{Z}の元の全てと一対一対応。
よって、$ X+ab\mathbb{Z}_{\geq 0}は$ (a-1)(b-1)以上の整数全てを含む。
$ p \neq 0 \lor q \neq 0 なる $ x=pa+qb について$ b-p \neq 0 \lor a-q \neq 0なる$ (b-p)a+(a-q)b=2ab-x\in Xが存在する。$ x<(a-1)(b-1)なる元に対して$ 2ab-x>2ab-(a-1)(b-1)=(a-1)(b-1)だから$ Sに含まれない非負整数の数は$ p \neq 0 \lor q \neq 0 なる $ xの半分を$ (a-1)(b-1)から引いた$ (a-1)(b-1)/2個である。