perl中非常大的数字的快速乘法

Question

我有50,000个号码(范围从0到50,000).我需要(这些数字的产品)MOD 1000000007.以下代码是如此微不足道,应该有其他方法.听说过"分而治之"的技巧,却不知道如何实施.

$ans *= ( $_ % 1000000007 ) foreach @array;
$ans %= 1000000007;

请建议.

Answer 1

结果$num % 1000000007将始终$num为小于1000000007的所有值.因此,如果所有值@array都在0 ... 50,000范围内,则此类计算是多余的.您必须执行两个步骤,而不是使用*=运算符:

$ans = ($ans % 1000000007) * $_ for @array;

但是要小心谨慎.对于任何非素数模数,总是存在模运算结果为零的风险,这当然会导致整个乘法产生零.我想你已经想过这个,因为1000000007似乎是一个素数,但我还是会提到它.

ETA:重复使用中间产品:

for (@array) {
    $ans *= $_;
    print "Before mod: $ans\n";
    $ans %= 1000000007;
    print "After mod : $ans\n";
}

请注意,您无需在此处复合运算符.