2

我有一个特定的问题，我得到了一个名为 N 的 T 数字列表（T 是输入的第一行），我必须((2^N)-1)%(10^9+7)为每个数字打印出来。以下限制适用：

1 ≤ T ≤ 100
1 ≤ N ≤ 100000000

我得到了低整数的正确答案，但不是高整数。我认为这与pow()math.h 中的函数有关，但我不确定。

这是我的代码：

#include <stdio.h>
#include <math.h>

int main(void) {
    unsigned int t, i;
    long long unsigned int ans, n, m = 1000000007;
    scanf("%u", &t);
    for (i = 0; i < t; ++i) {
        scanf("%llu", &n);
        ans = ((long long unsigned int)pow(2,n)-1)%m;
        printf("%llu\n", ans);
    }
    return 0;
}

所以基本上当我给我的程序这个输入时：

6
1
2
3
4
5
100000000

我得到输出：

1
3
7
15
31
582344007

我的输出的前 5 行是正确的，但我想在最后一行得到 494499947。

有关给出正确答案的 wolfram alpha 输出，请参见此处。

抱歉，如果我的问题微不足道，我仍在学习 C 的细节。

4

3 回答 3

4

结果pow(2, 100000000)超过 3000 万位。它不能转换为整数类型（偶数long long unsigned int） - 它太大了！

您将需要使用模幂来获得准确的结果。

于 2013-11-10T22:04:00.443 回答
1

您的方法既耗时又溢出大小 2^64（long long）。 正如您在问题中所说，您想找到 2^100000000。这将需要“100000000”这么多次迭代精确O(n)。所以更好的方法是使用模幂。它不仅在O(log n)时间内计算，而且还通过在中间步骤使用 mod 10^9+7 给出整数（long long）范围内的答案。

   mod=10^9+7;


 powermod(x,y)
         res:=1
             while(y>0)
                 if y&1
                    res=res*x%mod

                x=x*x%mod
                y=y>>1
         return res
于 2016-10-12T06:59:50.883 回答
0

您正在调用 pow，这需要双倍。如果你想要最大范围，至少在 Linux 上使用 powl ，这需要很长的两倍。您的程序缺少对溢出、范围错误等的检查。如果（看起来）您对结果的正确性感兴趣，那么您应该添加这些。我认为你只需要更仔细地重新阅读'man pow' :-)

于 2013-11-10T22:09:39.913 回答