18

私はシリーズを持っています

S = i^(m) + i^(2m) + ...............  + i^(km)  (mod m)   

0 <= i < m, k may be very large (up to 100,000,000),  m <= 300000

和を求めたい。結果に分母があり、存在しない可能性のある剰余逆数を見つける必要があるため、幾何学的累進 (GP) 式を適用できません (分母と m が互いに素でない場合)。

そこで私は、これらの累乗が k よりもはるかに短い長さのサイクルを作るという仮定を立てて、別のアルゴリズムを作成しました (これは剰余方程式であり、2,7,9,1,2,7,9 のようなものが得られるためです)。 1....) そして、そのサイクルが上記のシリーズで繰り返されます。したがって、0 から k まで反復する代わりに、サイクル内の数値の合計を見つけてから、上記の系列のサイクル数を計算して乗算します。そのため、最初にこの数を見つけi^m (mod m)てから、最初の要素に再び到達するまで、各ステップでモジュロを取りながら何度も乗算しました。

しかし、実際にアルゴリズムをコーディングすると、i の値によっては、非常に大きなサイズのサイクルが得られました。そのため、終了するまでに長い時間がかかったため、私の仮定は正しくありません。

では、私たちが見つけることができる他のパターンはありますか? (基本的に、k を反復処理したくありません。) 合計を求める効率的なアルゴリズムのアイデアを教えてください。

4

4 に答える 4

13

お気づきのように、任意のモジュラス m の計算を行うのは困難です。これは、多くの値が乗法逆 mod m を持たない可能性があるためです。ただし、慎重に選択された代替弾性率のセットについて解ける場合は、それらを組み合わせて解 mod m を取得できます。

p_1, p_2, p_3 ... p_nそれぞれp_iが異なる素数の冪乗になるようにm を因数分解する

各 p は異なる素数ベキであるため、それらは対ごとに互いに素です。各係数 p_i に関して級数の合計を計算できれば、中国剰余定理を使用してそれらを法 m を法とする解に再構築できます。

各素数べき乗モジュラスには、2 つの自明な特殊なケースがあります。

i^m が 0 mod に合同である場合p_i、合計は自明に 0 です。

i^m が 1 modp_iに合同である場合、合計は k mod に合同p_iです。

他の値については、等比数列の和に通常の式を適用できます。

S = sum(j=0 ～ k, (i^m)^j) = ((i^m)^(k+1) - 1) / (i^m - 1)

TODO: (i^m - 1) が互いに素であることを証明するp_iか、非自明な GCD がある場合の代替解を見つけます。p_iうまくいけば、それが素数ベキであり、m の約数でもあるという事実が、何らかの役に立つでしょう... Ifp_iが i の約数である場合。条件が成り立ちます。が素数の場合p_i(素数べき乗ではなく)、特殊なケース i^m = 1 が適用されるか、または (i^m - 1) に乗法逆数があります。

幾何学的合計式が一部p_iの に使用できない場合は、計算を再配置して、1 から k の代わりに 1 から k まで反復するだけでよくp_i、項が より長くない周期で繰り返されるという事実を利用できp_iます。

(シリーズには aj=0 項が含まれていないため、必要な値は実際には S-1 です。)

p_iこれにより、CRT の要件を満たす一連の合同 mod が得られます。それらを組み合わせて mod m の解にする手順は、上記のリンクに記載されているので、ここでは繰り返しません。

于 2009-10-05T23:21:27.190 に答える