ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

diverta 2019 Programming Contest D - DivRem Number

AtCoder プログラミング 競技プログラミング

D - DivRem Number

解法

この問題は「割り算して切り捨て」と「余り」の関連性に気付くととても考えやすくなります。実際、割り算して切り捨てたときに捨てられる部分は割った余りそのものです。

具体的に数式で表すと、 N を m で割った余りを r とすると \lfloor\frac{N}{m}\rfloor = \frac{N-r}{m} が成立します。つまり問題の条件式は \frac{N-r}{m} = r となり、これは整理して m = \frac{N}{r} - 1 となります。ただし、 N を m で割った余りが r であることから r \lt m も成立している必要があります。

m は整数で、右辺が整数になるためには r が N の約数である必要があります。そのため N の約数を列挙して、それを r としたときの m = \frac{N}{r} - 1 について「正かどうか」「本当に元の条件式を満たすか」を調べればよいです。

「本当に元の条件式を満たすか」を調べるには実際に計算してみても良いですし、 m = \frac{N}{r} - 1 かつ r \lt m であれば必要十分になるのでそれをチェックしても良いです。

約数列挙は計算量 O(\sqrt{N}) で行えるため、 N \le 10^{12} でも間に合います。

ACコード

Submission #5351859 - diverta 2019 Programming Contest

このコードでは条件を満たすかの確認に r \lt m を使っていますが、実際に計算してみるほうが安心できるのでオススメです。