代码之家 › 专栏 › 技术社区 › Hazior

C中的模块化立方体#

algorithm c#

Hazior · 技术社区 · 15 年前

我很难解决这个问题:

对于正数n,定义c(n) 作为整数x的个数,对于其中1<x<n和x^3=1 mod n。

当n=91时,有8个可能值对于x,即:9、16、22、29、53、74, 79, 81。因此,C(91)=8。

求正数的和 n<=10^11,其中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?或者我的逻辑错了?

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

5 回复 | 直到 10 年前

Eric Lippert 15 年前

让我把你的问题概括为两个问题:

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

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

其他人已经回答了第一部分,但总而言之:

问题1:数学。POW使用双精度浮点数,精确到小数点后15位。他们不适合做需要解决的问题 很完美 涉及的准确性 大整数 . 如果你尝试用双数计算1000000000000000-1,你会得到1000000000000000,这是对15位小数的精确答案,这就是我们所保证的。如果你需要一个完美准确的答案来处理大量的数据,请使用long来处理少于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不是999999999999,而是1000000000000000。

这就是建议1:编写代码,以便在调试器中轻松完成,并检查每个步骤,寻找似乎错误的步骤。

建议2:注意安静的、喋喋不休的疑问。当一些事情看起来不可靠或者有一点你不理解,调查它直到你理解它。

Brian 15 年前

维基百科有一篇关于 Modular exponentiation 你会发现信息丰富。iirc,python有内置的。C没有,所以您需要自己实现它。

jason 15 年前

不计算幂模 n 使用 Math.Pow ;您可能会遇到溢出问题以及其他可能的问题。相反,您应该从第一原则计算它们。因此,要计算整数的立方 i 模 n 先减少 我 模 n 一些整数 j 以便 我 与…一致 J 模 n 和 0 <= j < n . 然后迭代乘 J 减少模 N号 在每次乘法之后;要计算一个立方体,您将执行此步骤两次。当然,这是本机方法,但是您可以通过遵循经典的求幂算法,使用 exponentiation by squaring .

另外,就效率而言,我注意到您正在进行不必要的计算 Math.Pow(i, 3) - 1 两次。因此,至少要更换

if ((Math.Pow(i, 3) - 1) % intCount2 == 0) {
    if ((Math.Pow(i, 3) - 1) != 0) {
        Console.WriteLine(i);
        intHolder += i;
    }
}

具有

int cubed = Math.Pow(i, 3) - 1;
if((cubed % intCount2 == 0) && (cubed != 0)) {
    Console.WriteLine(i); 
    intHolder += i;
}

user159335 15 年前

嗯,有东西不见了,或者是打字错误…

“IntHolder1”大概应该是“IntHolder”,对于IntCount2=91,要得到8,增量行应该是:

intHolder ++;

Thomas Levesque 15 年前

我没有办法解决你的问题,但这里有一条建议:

不要在只涉及整数的计算中使用浮点数…类型 int ( Int32 )显然不足以满足您的需求,但是 long ( Int64 )应该足够了:你要操纵的最大数量是 (10 ^ 11 - 1) ^ 3 ,小于 10 ^ 14 ,绝对小于 Int64.MaxValue . 效益:
- 所有的计算都使用64位整数,这在64位处理器上应该是相当有效的。
- 所有的计算结果都是精确的,因为由于双精度数的内部表示没有近似值。

不要使用 Math.Pow 要计算整数的多维数据集… x*x*x 同样简单,而且效率更高,因为它不需要转换为/从双精度转换。不管怎样,我数学不是很好,但你可能不需要计算 X^ 3 …查看其他答案中有关模块求幂的链接