解释这一算法

。因此，从已经解决它的人那里领导，我在python中编写了下面的代码。解释这一算法

################################################ 
### http://www.codechef.com/problems/TAPALIN ### 
################################################ 
def pow(b,e,m): 
    r=1 
    while e>0: 
     if e%2==1: 
      r=(r*b)%m 
     e=e>>1 
     b=(b*b)%m 
    return r 
def cal(n,m): 
    from math import ceil 
    c=280000002 
    a=pow(26, int(ceil(n/2)), m) 
    if(n%2==0): 
     return ((52*(a-1+m)%m)*c)%m 
    else: 
     return ((52*(((a-1+m)*c)%m))%m+(a*26)%m)%m 
c=int(raw_input()) 
m=1000000007 
for z in range(c): 
    print cal(int(raw_input()),m)

pow的功能是Right-to-left binary method。我不明白的是：

280000002从哪里来的？
为什么我们需要执行如此多的mod操作？
这是一些我不知道的着名算法？

几乎每个在codechef上提交的代码都使用这个算法，但我无法破译它的工作。任何理论的链接将不胜感激。

我仍然无法弄清楚究竟发生了什么。 任何人都可以为这个公式/算法写一个伪代码吗？也帮助我了解此代码的时间复杂性。这让我吃惊的另一件事是，如果我写这个代码：

################################################ 
### http://www.codechef.com/problems/TAPALIN ### 
################################################ 
def modular_pow(base, exponent): 
    result=1 
    while exponent > 0: 
     if (exponent%2==1): 
      result=(result * base)%1000000007 
     exponent=exponent >> 1 
     base=(base*base)%1000000007 
    return result 
c=int(raw_input()) 
from math import ceil 
for z in range(c): 
    n=int(raw_input()) 
    ans=modular_pow(26, int(ceil(n/2))) 
    if(n%2==0): 
     print ((52*((ans)-1+ 1000000007)%1000000007)*280000002)%1000000007 
    else: 
     print ((52*((((ans)-1+ 1000000007)*280000002)%1000000007))%1000000007+(ans*26)%1000000007)%1000000007

这改善了从0.6secs到0.4秒性能。尽管最好的代码在0.0秒内运行。我非常困惑。

来源

2013-03-26 whizzzkid

数字280000002是25模10^9 + 7的模乘乘反算，因为我们知道10^9 + 7是素数，所以它只是使用pow(25, 10^9 + 7 - 2, 10^9 + 7)来计算。在这里阅读更多：http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

而且我们需要进行这么多模操作，因为我们并不想与之合作的大数字;-)

来源

2013-03-26 06:19:40 MostafaR

从未见过这种算法之前，但通过它与一些容易走测试用例开始揭示正在发生的事情（顺便说一下，我猜测每个人都在使用它，因为它是代码厨师的最佳答案，每个人都只是在复制它，我不认为你必须假设它是唯一的方法来做到这一点）。

回答您的问题：

哪里值280000002来自？

280000002的25模1000000007.的模乘法逆这意味着下面的一致性是真的

280000002 * 25 === 1 (mod 1000000007)

为什么我们需要进行这么多模操作？

可能只是为了不在处理巨大的数字。虽然在那里有一些额外的数学，似乎我只是让数字比他们需要的大，但最后看到我的笔记。理论上讲，你可以在最后做一个大型模组，并获得相同的结果，但是可能我们的小型CPU不会那样。

这是一些我不知道的着名算法？

我再次怀疑它。这不是一个算法，因为它是一个混搭的数学公式。说到数学，那里有一些东西对我来说是有问题的。这是一段时间，因为我搞砸了这个东西，但我很确定(52*(a-1+m)%m)将始终等于(52*(a-1)%m自52m mod m = 0。不知道为什么你会在那里添加那么多的数字，如果你摆脱了这一点，你可能会看到一些性能上的提升。

来源

2013-03-26 06:23:29

感谢您的信息。肯定地（52 *（a-1 + m）％m）=（52 *（a-1）％mi在如此之多的操作之间如此混乱，以至于我从未想到过，尽管这不是一个巨大的提升，这两个代码在0.6秒内执行都是正确的。 – whizzzkid 2013-03-26 07:29:02

解释这一算法

回答

相关问题