問題タブ [modular-arithmetic]

フェルマーの小定理によれば、a^(p-1) mod(p) は 1 です。したがって、a^k(p-1) mod(p) は、k 個の部分に分割し、係数を個別に適用することで 1 になります。 . 何か不足していますか？

モジュラー合同を解決できる C++ プログラムを構築しようとしています。

n^p = x (mod q ),

ここで、n は小さな数で、p と q は非常に大きな任意の素数です。これを何度も試みましたが、常にメモリ オーバーフローの問題が発生します。どんな助けでも大歓迎です。

配列 Array = {} があります。配列のサイズは n です

私の制約は次のようなものです：

n <= 100000 および配列_i <=100

配列内のすべての要素の積を見つける必要があります。積を変更する必要がある mod 値が与えられます。mod の値は常に変化し、この mod の値は常に n 以下です。

私の問題は、私が選択したときに、グローバル mod 値が R = 1000000000 (mod 制約よりもはるかに大きい) であり、製品がこの値を超えるたびに結果を変更することです。

しかし、私が得た結果がゼロである理由がわかりません。

私の質問は、そのような状況でどのように R を選択するかです。

配列に対して製品範囲クエリを実行するためのコードを作成しました。

注: この質問はMultiplication in a rangeの重複ではありません。私の問題は何か違う

このためのコードを書きましたが、

私が選択した R は、いくつかのテストケースに失敗していると確信しています。^{R も 10 18}で試しました。しかし、それでも同じ問題です。なぜこれが起こっているのか分かりませんか？

私の質問は、RI が選択した問題なのか、それとも各テスト ケースで異なる M が渡される問題なのかということです。

注: 本当に解決策を期待しているのではなく、手がかりを期待しているだけです

よろしく