C問題

大きな数を扱うときに文字列として扱う以外の方法を学んだのでメモ。

等比数列として考える

今回のC問題のi番目は、

$7 \times (1 + 10 + 10^2 + \dots + 10^{i-1}) \\ = \frac{7(10^i -1)}9$

と書ける。

$10^{999982}$ などといった巨大な値を直接 $L$ で割ろうとするべきではありません。その代わりに、 10ⁱ を $L$ で割った余りを $10$ 倍して $L$ で割れば、 10ⁱ+1 を $L$ で割った余りが求まります。

仕切りを入れて、部分問題にわける。

sum(ceil(A_i / X) - 1) < kと条件を書き換えて、二分探索

...