c++ - 弾性率の繰り返しサイクル

Question

^1111..n mod Mの値を効率的に求める方法はありますか? 10 ⁰ mod M + 10 ¹ mod M + 10 ² mod M + 10 ³ mod M + ...10 ⁿ mod M
を見つけるために、繰り返し 2 乗をいつでも使用できます 。これよりも高速な方法はありますか?

Answer 1

10 が冪極の場合 (M = 2^a * 5^b の場合)、10 の累乗は最終的に 0 になるか、ある時点で循環を開始します。(実際には、0,0,0... もサイクルです。) サイクルの長さは、M-1 まで大きくすることができます。したがって、反復値が観察されるまでべき乗を計算し、単純な代数を使用して、観察された個別のべき乗に関して項を収集します。

これにより、複雑さが O(n) から O(M) に低下すると思います。これは明らかに、大きな n の改善です。