c# - 我需要在 C# 中计算 (9173501*9173502*9173504)%9173503；

Question

我需要(9173501 * 9173502 * 9173504) % 9173503用 C# 计算；result = 2 但 C# 无法计算它。如果您有任何想法，请帮助我。

Answer 1

没有必要使用大整数。

使用这个公式：

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

这样，您可以将模数应用于两个数字的乘积，每个数字都是< 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为：

• 2 对于每 n > 2
• 0 代表 n = 1, 2

这意味着不仅是(9173501 * 9173502 * 9173504) % 9173503 = 2，而且13^127^61 * (13^127^61 + 1) * (13^127^61 + 3) % (13^127^61 + 2)也是2，这很可能是用 C# 或其他编程语言无法计算的。