ARC091 D Remainder Reminder

Submission #2868393 - AtCoder Regular Contest 091

所見

さんすう

問題概要

aをbで割った余りがK以上になるN以下の整数の組(a,b)の個数を求めよ。

取った方針

bを固定すると、aをbで割った余りはaが1の場合から順番に1,2,...b-1,0,1,2...とループする。
1,2...0までの区間にK以上のあまりはb-K個あることを考えると、条件を満たすaは(N/b)*(b-K)個ある。
また、b個の組が作れない最後の(N%b)個の中にはmax(N%b - max(K-1, 0), 0)個の条件を満たすaがある。なぜなら、最後のN%b個のaをbで割った余りは1,2,...xなる列をなし、最初のK-1個はあまりがKより小さくなるからである。
よって、あるb(ここではpとおく)についてO(1)で(N / p)*(p - K) + max((N%p - max(K - 1, 0LL)), 0LL)組の解が存在するとわかる。
これをすべてのbについて求めればよいので、O(N)。

正しい方針(解説の方針)

同上

得られた知見

・制約から何についてなら全探索できるかを考える
・剰余->一定間隔でループする、被除数を1ずつ増やすと剰余も1ずつ増える(当たり前)という強い性質を持つ

解くのに必要な要素

・剰余は一定間隔でループする
・さんすうはてきとうに文字を置いて一般的に考える
・一般的に考えればそれをそのままハードコードして終了がち(プロコンとは)

周辺調査によって得られた知見

なし