Python中的模幂运算 [英] Modular Exponentiation in Python

问题描述

我试图使用Python 2.7.9作为我的编码语言来解决SPOJ上的ZSUM问题，并设计了一个程序来解决这个问题。由于代码可以完美运行，但是会给评委一个标题，所以我认为它不够快。是否可以优化以下代码以满足法官的要求，或者使用Python无法克服挑战。

I was trying to solve the ZSUM problem at SPOJ using Python 2.7.9 as my coding language and designed a program to do so. As the code runs perfectly but gives a TLE at the judge, I guess it is not fast enough. Is there is possible to optimize the below code to meet the judge requirement or it is impossible to beat the challenge using Python.

链接到问题： http://www.spoj.com/problems/ZSUM/

def zsum(n,k):
  a=2*pow(n-1,k,10000007)
  b=pow(n,k,10000007)
  c=2*pow(n-1,n-1,10000007)
  d=pow(n,n,10000007)
  zsum=(a+b+c+d)%10000007
  print zsum

def main():
  while True:
    n,k=map(int,raw_input().split())
    if n==k==0:
        break
    else:
        zsum(n,k)
 main()

推荐答案

由于总共2335个成功的提交中有零个被接受的python解决方案，所以我认为，无论您如何优化解决方案，它不太可能被python接受。尽管python是一种非常有用的语言，但它在编程竞赛中并不受欢迎，因为它非常慢（例如，与C / C ++相比）。如果您知道如何使用C ++进行编码，则尽管应该编写自己的模幂运算程序，但也应该一定要尝试一下。

Since there are zero accepted python solutions in a total of 2335 successful submissions, i think, no matter how much you optimise your solution, it is unlikely to manage to get accepted with python. Although python is a very useful language, it is not preferred in programming contests, as it is extremely slow (compared to C/C++ for instance). If you know how to code in C++ you should definitely give it a shot, although you must write you own modular exponentiation procedure.

这篇关于Python中的模幂运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！