c - 出力のモジュロ演算

Question

プログラムの出力が非常に大きいと推定されるほとんどのコーディング競技では、通常、出力を10000007（またはその場合は素数）で割るように指示されます。同じ番号が100004として与えられていることがわかりました（つまり、素数ではありません）。

Answer 1

素数は2つの理由で使用されます。1つの理由は、素数を法とする整数が数学フィールドを形成することです。フィールドの算術は、整数の算術のように多くの方法で機能します。これにより、特定のコンテストの問題でフィールドが役立ちます。そうしないと、使用されるシーケンスが崩壊する場合があります。特定の算術演算では、ゼロ、他の些細な結果、または必要以上に単純な結果が生成される場合があります。これは、係数の因数に基づいて数値が発生し、ある程度の減少または除去が発生するためです。

もう1つの理由は、特定のサイズの整数の算術演算をプログラマーに強制することです。合成数が使用された場合、大きな整数を使用した算術に頼らない他の手法を使用できます。

たとえば、13 ²がモジュロ35であるかを知りたいが、3桁の数値を処理できない非常に小さなプロセッサしかないため、13 ² =169を計算できません。

35 = 5•7であり、13は5を法とする3と7を法とする6に合同です。13の2乗を計算する代わりに、これらの剰余の2乗を計算できます。これは、^132が32 =に合同であることを示しています。 9 = 4モジュロ5であり、6 ² = 36 = 1モジュロ7と合同です。これらの剰余を組み合わせるには、追加の知識が必要です（拡張ユークリッドアルゴリズム）。これらの特定の数値について、5の留数に21を掛け、7の留数に15を掛けて、4・21 + 1・15 = 99を得ることができます。35を法として減らすと29が得られ、これが答えです（132の留数）^。モジュロ35）。

モジュラスがプライムの場合、この算術の回避は利用できません。素数モジュラスでは、基本的に、モジュラスの2乗までの数値で算術を使用する必要があります（または時間のかかる回避策）が、複合モジュラスでは、モジュラスの2倍までの小さい数値で算術を使用できます。