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

发布时间：2020-12-15 23:22:06 所属栏目：大数据来源：网络整理

导读：我有50,000个号码(范围从0到50,000).我需要(这些数字的产品)MOD 1000000007.以下代码是如此微不足道,应该有其他方法.听说过“分而治之”的技巧,却不知道如何实施. $ans *= ( $_ % 1000000007 ) foreach @array;$ans %= 1000000007; 请建议. 解决方法对于小

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

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

请建议.

解决方法

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

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

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

ETA：重复使用中间产品：

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!