vocabulary の解説 と同様に $N \times (N - 1) \times (N - 2) \times \cdots \times (N - i + 1)$ を $P(N, i)$ と表記します。

解説

入力の受け取りには多倍長整数を使用するか、($N$ を $10^{18}$ で割った余りしか出力に影響しないことから) $N$ を文字列として受け取り、その下 $18$ 桁のみを 64 bit 整数に変換するなどの処理を行えばよいです。

vocabulary と同様、この問題も $\displaystyle\sum_{i = 1}^N P(N, i)$ を $10^{18}$ で割った余りを求める問題となります。

ここで、任意の整数 $m, n$ に対して $m$ を $10^{18}$ で割った余りと $(m + n \cdot 10^{18})$ を $10^{18}$ で割った余りは等しいことから、$P(N, i)$ が $10^{18}$ の倍数となる場合にはその項の計算を行わなくても出力に影響しないことが分かります。そこで、$P(N, i)$ が $10^{18}$ の倍数となる $i$ の条件を見つけてその部分の計算を省略することを考えます。

$P(N, i)$ は連続する $i$ 個の整数の積であるため、$10^{18} \leq i$ なる $i$ について $P(N, i)$ が $10^{18}$ の倍数となることは直ちに分かります(連続する $10^{18}$ 個の整数の中には $10^{18}$ の倍数が含まれるため)。したがって、$\displaystyle\sum_{i = 1}^{\min(N, 10^{18} - 1)} P(N, i)$ を計算するだけで答えが得られます。

もう少し考えると、$10^{18} = 2^{18} \times 5^{18}$ より連続する $10^{18}$ 個の整数でなくても $2$ の倍数と $5$ の倍数がそれぞれ $18$ 個以上含まれるような区間の整数の積は $10^{18}$ の倍数となることが分かります。例えば連続する $90$ 個の整数に $2$ の倍数と $5$ の倍数はそれぞれ $18$ 個以上含まれるので、$90 \leq i$ なる $i$ について $P(N, i)$ は $10^{18}$ の倍数となります。(更に言うと、連続する $25$ 個の整数の中には $25 = 5^2$ の倍数が $1$ つ含まれ、その分 $5$ の素因数を「稼げる」ため $i$ の条件は $75 \leq i$ で十分です。)

以上より $\displaystyle\sum_{i = 1}^{\min(N, 74)} P(N, i)$ を $10^{18}$ で割った余りを計算すればよく、この計算は十分高速に行えます。

解答例 (C++)

---

このようにすると、法とする値 (この問題では $10^{18}$) が $\displaystyle\prod_{i = 1}^{n} p_i^{q_i}$ と素因数分解されるとき(整数のコピーや四則演算等の操作の時間計算量が $O(1)$ であることを仮定すると) 時間計算量 $O \left(\displaystyle\max_{1 \leq i \leq n} p_i \cdot q_i \right)$ でこの問題を解くことができます。

例えば「$10^9$ で割った余りを求めよ」という問題も同様に解くことができますが、「$10^9 + 7$ で割った余りを求めよ」という問題をこの方法で解いて実行時間制限に間に合わせることは厳しいです($10^9 + 7$ は大きな素数であるため)。