1

我正在寻找范围：pow(2,i)除了 MOD =1000000007i0<=i<=100000.i

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

因为i=100000功率值不会大于 MOD 吗？

如何正确储存电源？

手术对我来说似乎不可行。i=70我猜我得到了最大的正确值。

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

4

2 回答 2

2

只要您的模值小于数据类型容量的一半，就永远不会超过。那是因为您取 range 中的前一个值，将其0..1000000006加倍，然后对其重新取模，使其回到相同的范围。

但是，我不能保证更高的值不会给您带来麻烦，考虑到简单的替代方案，它比我准备投资的更多的数学分析。您可能会花费大量时间进行分析、检查和调试，但最好一开始就不要让问题发生。

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

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

如果您想要一种简单（且有效）的方法来执行此操作，以下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部分是问题的“肉”，它创建了两个的大幂，并以您提供的数字为模输出它们。该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,
};
于 2015-05-18T06:55:23.110 回答
0

如果您注意到您的模数可以存储在 int 中。MOD=1000000007（十进制）等价于 0b00111011100110101100101000000111，可以 32 位存储。

 - i      pow(2,i)        bit representation 
 - 0            1         0b00000000000000000000000000000001
 - 1            2         0b00000000000000000000000000000010 
 - 2            4         0b00000000000000000000000000000100 
 - 3            8         0b00000000000000000000000000001000
 - ...
 - 29   536870912         0b00100000000000000000000000000000

当 pow(2,i) 大于您的 MOD=1000000007 时，棘手的部分开始了，但是如果您知道当前的 pow(2,i) 将大于您的 MOD，您实际上可以看到 MOD 之后位的样子

 - i      pow(2,i)  pow(2,i)%MOD      bit representation
 - 30   1073741824  73741817    0b000100011001010011000000000000
 - 31   2147483648  147483634   0b001000110010100110000000000000
 - 32   4294967296  294967268   0b010001100101001100000000000000
 - 33   8589934592  589934536   0b100011001010011000000000000000

所以如果你有 pow(2,i-1)%MOD 你可以在 pow(2,i-1)%MOD 上做 *2 直到你下一个 pow(2,i) 将大于 MOD。

在 i=34 的示例中，您将使用 (589934536*2) MOD 1000000007 而不是 (8589934592*2) MOD 1000000007，因为 8589934592 不能存储在 int 中。

另外，您可以尝试位运算而不是 pow(2,i) 的乘法。与 2 的乘法相同的位操作是向左移位。

于 2015-05-18T07:26:38.977 回答