今回扱うのはyukicoder contest 486 オムニバス C問題 No.3310 mod998です。公式解説に載っていない別解を紹介します。

問題の概要

正確な問題文はこちらです。

$\sum_{i=0}^{K} N^i \bmod 998$を求めよ。

前置き

この問題はマルチテストケースで、$K$の上限は$10^{10^5}$です。公式解説で扱われている方法はサイクル検出で周期性を用いる計算方法ですが、ここでは等比数列の和の公式を駆使した解法を紹介します。他にも行列累乗を用いる方法もあります。

準備

まず等比数列の和の公式から \[ \sum_{i=0}^{K} N^i = \left\{ \begin{array}{ll} K+1 & (N=1) \\
\frac{N^{K+1} - 1}{N - 1} & (N \neq 1) \end{array} \right. \] です。これを$998$で割った余りを求めれば良いです。

解説

$N=0$の時は$1$が答えです。

$N=1$の時はまず$K \bmod 998$を求めます。これは$K$を文字列として受け取って下の桁から順に見つつ$10$冪を法$998$で累積積により計算していけば良いです。その後$1$を法$998$で足せば良いです。

$N>1$の時は$N-1$で最後に割りたいので、法$998(N-1)$で$N^{K+1}$を求めます。これは$K$を文字列として受け取って下の桁から順に見つつ$N$の$10$冪冪を繰り返し$10$乗法のつもりで計算すれば良いです。この値に法$998(N-1)$で$1$を引くと、$(N^{K+1}-1) \bmod 998(N-1)$が求まります。$N^{K+1}-1$は$N-1$で割り切れるので$(N^{K+1}-1) \bmod 998(N-1)$も$N-1$で割り切れ、その商は

\[ \frac{N^{K+1}-1}{N-1} \bmod 998 \]

に他なりません。このように分母に来る値をあらかじめ法に掛けておくことで割り算が可能になるテクは合成数を法とする問題で役立つので覚えておきましょう。

この解法の計算量は、想定している実装において$O(\log_{10} K)$です。

なお、上記の解法はc++などで実装する想定です。pythonで実装する場合は多倍長整数で直接$K$が扱えるので、$(K+1) \bmod 998$も$N^{K+1} \bmod 998(N-1)$も組み込み関数で直接計算できます。

感想

等比数列の和の公式、法が素数でなくても臆せず使っていきましょう。

実装例

• c++: https://yukicoder.me/submissions/1129111
• python: https://yukicoder.me/submissions/1129224

類題

• ★2 No.2649 [Cherry 6th Tune C] Anthem Flower（数値の文字列受け取り＋合成数法での割り算）
• ★3 No.2994 べき内積（繰り返し冪乗法）
• ★4.5 No.2993 冪乗乗 mod 冪乗（合成数法での割り算）

自分用覚え書き

github pagesで数式を使う際は、閉じカッコと半角アンダーバーの間に半角スラッシュを入れないとmarkdownからhtmlへの翻訳の仕様でバグるらしい。

数式環境をくくる大括弧と数式環境内の中括弧や半角空白や濃度のシャープは半角スラッシュ２つ、改行は半角スラッシュ５つ、その他は基本的に半角スラッシュ１つで良さそう。htmlとmathjaxの関係が難しい。

inline数式内の縦棒はlvertなどを使わないとmarkdownの表と認識される。

arrayとalignはどちらも使える。arrayが使えない気がしてしまったのは中括弧につける半角スラッシュの個数を間違えていたから。alignはアンパサンドを等号の右側につけて半角空白を２つ入れると幅がちょうど良さそう。arrayなしだとアンパサンドは使えない。