c++ - 计算和存储非常大数的幂

Question

我正在寻找 pow(2,i)其中 i范围:0<=i<=100000. 除i有MOD=1000000007

powers[100000];
powers[0]=1;
for (i = 1; i <=100000; ++i)
{
  powers[i]=(powers[i-1]*2)%MOD;
}

i=100000 power value 不会变得大于 MOD 吗？

如何正确储存能量？

这个手术在我看来不可行。我得到的正确值高达 i=70我猜最大。

我必须找到 sum+= ar[i]*power(2,i) 并最终打印 sum%1000000007，其中 ar[i] 是一个附加数组，其中包含一些高达 10^5 的大数

Answer 1

只要你的模值小于你数据类型容量的一半，就永远不会被超过。这是因为您采用 0..1000000006 范围内的先前值，将其加倍，然后对其重新求模，使其回到相同的范围。

但是，我不能保证更高的值(value)不会给您带来麻烦，考虑到简单的替代方案，这是比我准备投资更多的数学分析。您可以花大量时间分析、检查和调试，但最好不要让问题首先发生。

替代方案？我倾向于使用预生成方法(让一个程序预先完成繁重的工作，将预生成的值插入到一个数组中，该数组可以从您的真实程序轻松快速地访问)。

通过这种方法，您可以使用经过充分测试且已知可处理大量值的工具。由于此数据不会更改，因此每次程序启动时都计算它是没有用的。

如果你想要一个简单(和高效)的方法来做到这一点，下面的 bash 脚本结合 bc 和 awk 可以做到这个:

#!/usr/bin/bash

bc >nums.txt <<EOF
    i = 1;
    for (x = 0;x <= 10000; x++) {
        i % 1000000007;
        i = i * 2;
    }
EOF

awk 'BEGIN { printf "static int array[] = {" }
           { if (NR % 5 == 1) printf "\n    ";
             printf "%s, ",$0;
             next
           }
     END   { print "\n};" }' nums.txt

bc 部分是问题的“核心”部分，它计算 2 的大幂次，并以您提供的数字为模输出它们。 awk 部分只是将它们格式化为 C 风格的数组元素，每行五个。

只需获取它的输出并将其放入您的代码中，瞧，您就拥有了一个可用于快速查找的编译时间消耗数组。

在我的盒子上生成数组只需要一秒半，然后您永远不需要再做一次。您也不必担心模数数学的变幻莫测:-)

static int array[] = {
    1,2,4,8,16,
    32,64,128,256,512,
    1024,2048,4096,8192,16384,
    32768,65536,131072,262144,524288,
    1048576,2097152,4194304,8388608,16777216,
    33554432,67108864,134217728,268435456,536870912,
    73741817,147483634,294967268,589934536,179869065,
    359738130,719476260,438952513,877905026,755810045,
    511620083,23240159,46480318,92960636,185921272,
    371842544,743685088,487370169,974740338,949480669,
    898961331,797922655,595845303,191690599,383381198,
    766762396,533524785,67049563,134099126,268198252,
    536396504,72793001,145586002,291172004,582344008,
    164688009,329376018,658752036,317504065,635008130,
    270016253,540032506,80065005,160130010,320260020,
    640520040,281040073,562080146,124160285,248320570,
    :
    861508356,723016705,446033403,892066806,784133605,
    568267203,136534399,273068798,546137596,92275185,
    184550370,369100740,738201480,476402953,952805906,
    905611805,
};