c# - C# 中的模块化立方体

Question

我很难解决这个问题:

For a positive number n, define C(n) as the number of the integers x, for which 1 < x < n and x^3 = 1 mod n.

When n=91, there are 8 possible values for x, namely : 9, 16, 22, 29, 53, 74, 79, 81. Thus, C(91)=8.

Find the sum of the positive numbers n <= 10^11 for which C(n) = 242.

我的代码:

double intCount2 = 91;
double intHolder = 0;

for (int i = 0; i <= intCount2; i++)
{
    if ((Math.Pow(i, 3) - 1) % intCount2 == 0)
    {
        if ((Math.Pow(i, 3) - 1) != 0)
        {
            Console.WriteLine(i);
            intHolder += i;
        }
    }
}
Console.WriteLine("Answer = " + intHolder);
Console.ReadLine();

这适用于 91，但是当我输入任何带有很多 0 的大数时，它会给出很多我知道是错误的答案。我认为这是因为它非常接近 0，以至于它四舍五入为 0。有什么办法可以看出某些东西是否恰好为 0？还是我的逻辑有问题？

我知道我需要一些优化来让它提供及时的答案，但我只是想让它产生正确的答案。

Answer 1

让我将您的问题概括为两个问题:

1) 这个程序具体有什么问题？

2) 如何找出程序中的问题所在？

其他人已经回答了第一部分，但总结一下:

问题 #1:Math.Pow 使用 double float ，它只能精确到大约 15 位小数。它们不适合处理涉及大整数的需要完美精度的问题。如果您尝试计算 1000000000000000000 - 1，以 double 计算，您将得到 1000000000000000000，这是小数点后 15 位的准确答案；这就是我们的保证。如果您需要一个非常准确的答案来处理大数，请对小于 100 亿的结果使用长整型，或者在下一版本的框架中使用 System.Numerics 中的大整数数学类。

问题 #2:有更有效的方法来计算不涉及生成大量数字的模指数；使用它们。

但是，我们这里遇到的是“授人以鱼”的情况。教你钓鱼更好；了解如何使用调试器调试程序。

如果我必须调试这个程序，我会做的第一件事就是重写它，以便沿途的每一步都存储在一个局部变量中:

double intCount2 = 91; 
double intHolder = 0; 

for (int i = 0; i <= intCount2; i++) 
{ 
    double cube = Math.Pow(i, 3) - 1;
    double remainder = cube % intCount2;
    if (remainder == 0) 
    { 
        if (cube != 0) 
        { 
            Console.WriteLine(i); 
            intHolder += i; 
        } 
    } 
} 

现在在调试器中使用一个您知道答案是错误的示例逐步执行它，并查找违反您的假设的地方。如果这样做，您很快就会发现 1000000 的立方减 1 不是 99999999999999999，而是 1000000000000000000。

这就是建议 #1:编写代码以便在调试器中轻松单步执行，并检查每一步以寻找似乎错误的步骤。

建议 2:注意那些悄悄唠叨的疑虑。当某些东西看起来很狡猾或者有一点你不明白的时候，调查它直到你理解它。