はじめに

CodeIQというところでプログラミング問題「ディビジョン・サム」に解答しましたので、ネタバレです。

問題

今回は次のような問題でした。

出題者のkawazoeさんの解説にもありますが、素数$p$に対して$f(n,p)=\lfloor \frac{n}{p} \rfloor +\lfloor \frac{n}{p^2} \rfloor +\lfloor \frac{n}{p^3} \rfloor + \cdots$ とすると、

$$ F(n)=\prod_{p:prime}\frac{p^{nf(n,p)+1}-1}{p-1} $$

ということで、今回は1,000,003 ( 素数 ) で割った余りを求めるので、上述の$f(n,p)$と、modpow ( mod でのべき乗 )、modinv ( mod での逆数 ) を実装すれば良いことになります。
modinvについては、$p-1$による割り算の代わりですね。

なお、注意事項として、巨大な$n$に対しては$p\equiv 1\,\,mod\,1000003$となることがあって、ゼロ割になってしまうので、そこだけ除かなければなりません。

ということで実装です。

nの大小によって、方式を変えています。

nが小さい所では、modpowは素直にバイナリ法で、modinvは拡張ユークリッドの互除法で行っています。なお、modinvについては最後に1回まとめてやれば十分です。

しかし、( 用意されたテストケースでは不要なのですが )、n が大きい所では高速化のために、べき乗と対数 ( 離散対数 ) の結果を全て計算して配列に保存してしまいます。
分かり易いことに、mod 1000003では、2 が生成元になっているので、2 のべき乗を計算していけば良いのです。

そうすると、modpow も modinv も配列を引くだけで済みますから、高速化になるということです。ただし、これは n が小さいところでやってしまうと、配列を用意する分のコストが大きいですから、却って遅くなります。( まあ当然ですね )

あ、ちなみに n が 1000002の倍数の時は$\prod$の各項が必ず1になりますから、何も計算せずに1を出力すれば終わります。つまり、どんな巨大な n であっても ( ごく一部ですが ) $O(1)$で処理できるということですね!

なお、n がかなり大きくなると、$\prod$の項の中で0になるもの ( つまり $p^{nf(n,p)}\equiv 1$ になるもの ) が現れる可能性が高くなり、つまり答えが0になりやすくなります。( ただし 1000002 の倍数の時は除きます )

ある程度大きくなれば必ず0になるんじゃないかな…と思ったのですが、そこまで確かめることはできませんでした。実際どうなんでしょうね。