c# - C# で (9173501*9173502*9173504)%9173503 を計算する必要があります。

Question

(9173501 * 9173502 * 9173504) % 9173503C# で計算する必要があります。結果 = 2 ですが、C# では計算できません。何かアイデアがあれば、私を助けてください。

Answer 1

大きな整数を使用する必要はありません。

次の式を使用します。

(x * y) % k = ((x % k) * (y % k)) % k

このようにして、それぞれが になる 2 つの数値の積にモジュロを適用できる< 9173503ため、この積は に収まりlongます。

注:同じことが足し算にも当てはまります:

(x + y) % k = ((x % k) + (y % k)) % k

そして、わずかな変更を加えた減算:

(x - y) % k = ((((x % k + k) % k) - ((y % k + k) % k)) % k + k) % k

ただし、除算には当てはまりません。

(4 / 2) % 3 = 2
4 mod 3 = 1
2 mod 3 = 2
1 / 2 != 2

Answer 2

計算を開始する前に、数値を BigInteger に変換します。

Console.WriteLine((new BigInteger(9173501)*9173502*9173504)%9173503);
// Output: 2

Answer 3

なしで直接計算することはできませんBigIntegerが、数学的には次と同等です。

((long)9173501 % 9173503) * (9173502 % 9173503) * (9173504 % 9173503)  % 9173503

Answer 4

これは数学の問題であり、プログラミングの問題ではありません。

ご覧のとおり、数値は互いに非常に近いため、置き換えると次のn = 9173503ようになります(n-2)(n-1)(n+1) % n。

括弧を開くと、次の多項式が得られます。n^3 - 2*n^2 - n + 2残りは次のようnになります。

• n > 2 ごとに 2
• n = 1、2 の場合は 0

これは、 だけ(9173501 * 9173502 * 9173504) % 9173503 = 2でなく も13^127^61 * (13^127^61 + 1) * (13^127^61 + 3) % (13^127^61 + 2)意味し2ます。これは、C# や他のプログラミング言語では計算できない可能性が最も高いです。