けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

p で割って r 余る数のうち x 以上となる最小の数

なんか登場頻度高い割にいつも混乱するので...ちょっとちゃんと整理したいなと。。。
なんかこうすべきというのがあったらちゃんと勉強したいん。

r = 0 のとき

 p の倍数のうち、 x 以上となる最小の値を求めたい。
これはいわゆる「 x p で割って、あまりを切り上げる処理」に相当するのでわかりやすい

(x + p-1) / p * p

でよさそう。

一般のとき

問題を「 p の倍数のうち、 x-r 以上となる最小の数」としても一緒なので、

(x - r + p-1) / p * p + r

とすればよさそう。 x \le r の場合でもちゃんと  r と求められる。

p で割って r 余る数のうち x 未満となる最大の数

AGC 026 B - rng_10s (600 点) で使った形だけど、上のから  p 引けば OK。

(x - r + p-1) / p * p + r - p

ただし、上述の問題の場合、 x がすでに  p の倍数であることがわかっている、という特殊な状況だったので、

x + r - p

でよかった。