概要

考察に詰まったら，手を動かして実験してみましょう．

問題原案：uni_kakurenbo

解説

$P \leq Q$ としても一般性は保たれますから，以下は $P \leq Q$ とします．

$x \bmod P < P \leq Q$ より $(x \bmod P) \bmod Q = x \bmod P$ ですから，条件 $x \bmod P = (x \bmod Q) \bmod P$ を満たす $K$ 未満の非負整数 $x$ の個数を求めればよいです．

非負整数 $k$ に対して $kQ \leq x < (k + 1)Q$ の場合を考えます．(これですべての場合を網羅できます．)

$x \bmod Q = x - kQ$ より， $kQ \bmod P = 0$ すなわち $kQ$ が $P$ の倍数であることが必要十分です．
これは $k$ が $\frac{P}{\gcd \, \{\, P,\,Q \,\}}$ の倍数であると言い換えることができます．

以上より，周期 $Q\frac{P}{\gcd \, \{\, P,\,Q \,\}} = \mathrm{lcm} \, \{\, P,\,Q \,\}$ ごとに，幅 $Q$ の区間で条件を満たす $x$ が現れるとわかりました．

したがって答えは $Q \left \lfloor \frac{K}{\mathrm{lcm}\, \{\, P,\,Q \,\}} \right \rfloor + \min \, \{\, Q, K \bmod \mathrm{lcm} \, \{\, P,\,Q \, \} \,\}$ です．

解説：uni_kakurenbo

実装例