rd Problem

ある整数$n$に操作を行って生まれる整数は$n+d$と$n \times r$の高々$2$つです． よって，$1$以上$y$以下の各整数を頂点とみなし， $1 \leq n \leq y$に対して$n$から$n+d$と$n$から$n \times r$に有向辺を張ったグラフを考え， $1$から$y$までの最短距離を計算すればよいです． これは，幅優先探索を用いて実装することができます．

また，このグラフは各頂点から高々$2$本の有向辺しか張られていないことから， 全体でも高々$2y$本の有向辺しかありません． よってこれを陽にもってDijkstra法によっても計算することができます．