c - 简单的乘法，但编译器需要一分钟以上才能产生答案

Question

我的代码花费了太多时间，并且可能在一定限制后给出错误的答案。我观察到的是在我给出 N>50000 之后代码变慢了。

int solve(int N)
{
    long long int temp=0;
    long long int sum=0;
    const long long int mod=1000000007;

    for(int i=1;i<=N;i++)
    {
        for(int j=i;j<=N;j++)
        {
                temp=0;
                if((i&j)==0)
                {
                temp=i*j;
                sum=sum+temp;
                }
        }
    }
    return sum%mod;
}

1. 我正在努力为N>=1 to N<=200000.

2. 会不会是变量 sum 超出long long int了某个限制后的范围？

标签： c

Answer 1

temp=i*j;

因为i,j都是 type int，所以这个乘法是作为int（可能有符号的 32 位）完成的，如果它溢出最大的int(2**31-1) 那么你有未定义的行为并且肯定不会得到正确的答案。一点快速的数学表明，一旦N超出您提到46340的范围，就会发生这种情况。50000结果分配给类型变量的long long int事实不会改变i*j评估子表达式的方式，因此它不能解决您的溢出问题。

要使乘法完成long long int（至少 64 位），您必须转换一个或两个操作数：

temp = ((long long int)i) * j;

（强制转换比乘法具有更高的优先级，因此您实际上可以编写temp = (long long int)i * j;，但我倾向于发现这不太容易阅读。）

这可以解释“可能是错误的答案”，但与缓慢无关，正如其他人提到的那样，缓慢来自您的二次算法。然而，即使N=200000它在我的电脑上完成大约 8 秒。确保您使用的是高质量的优化编译器，并且您已启用优化。

不过，您关于溢出sum的问题 (2) 不是问题。每个被加数i*j最多为，这样的被加数N**2最多有N，所以 的最大值最多sum为N**3。您可以验证它200000**3仍然比 小得多2**63。