數學解：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