数学解：48

Question

问题来自黑客排名，我想数学解...

找到该系列的最后十个位数...

1^1 + 2^2 + 3^3 + ⋯ + N^N 

如果N太大大数

as where 1 <= N <= 2000000 

我有代码循环N，但它需要太多的时间来完成N> 1000000。

任何想法，以减少时间？

code: 
n = int(input()) 
if(n>=1 and n<=2*1e6): 
    s=0 
    for i in range(1, n+1): 
     s+=(i**i) 
    print(s%10000000000) 

Answer 1

这看起来像Python，所以我假设这就是你正在使用的（你应该用你正在使用的语言标记你的问题）。

最大的问题是，i**i是巨大的，所以Python使用大整数来跟踪一切。由于2e6 ^（2e6）有12602060个数字，因此计算速度太快（并且超过您需要的10个数字）。这也意味着我将模数转换成循环的建议可能没有帮助。

解决的办法是，当你服用幂（详见Modular exponentiation取模。一些实现arehere。使用Python使它更简单，因为你不必担心整数溢出（其中，具有讽刺意味的是什么原因导致你原来的问题）

但是Python的使这更容易，因为pow允许你指定一个可选的模所以，你可以重写你的原始代码为：。

n = int(input()) 
if (1<=n<=2e6): 
    s = 0 
    for i in range(1,n+1): 
    s += pow(i,i,10**10) 
    print(s%(10**10)) 

但是我们可以简化这更进一步河Python也有一个sum功能，让你可以使用一个列表的理解和把上面的

n = int(input()) 
if (1<=n<=2e6): 
    s = sum(pow(i,i,10**10) for i in range(1,n+1)) 
    print(s%(10**10)) 

但是这是愚蠢分配一个变量只有一步。所以，你会重写为

n = int(input()) 
if (1<=n<=2e6): 
    print(sum(pow(i,i,10**10) for i in range(1,n+1)) % 10**10) 

但是，你可能更愿意使用Python的命令行界面，而不用担心检查输入：

sum(pow(i,i,10**10) for i in range(1,2*10**6+1)) % 10**10