来自 Project Euler 的问题 48 描述：
系列，1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317。找到系列的最后十位，1^1 + 2^2 + 3^3 + ... + 1000^1000。
我刚刚在 Python 中使用单线解决了这个问题：
print sum([i**i for i in range(1,1001)])%(10**10)
我几乎立即就这样做了，因为我记得除法 mod n 在 Python 中非常快。但我仍然不明白这在幕后是如何工作的（Python 做了哪些优化？）以及为什么这么快。
你能给我解释一下吗？该mod 10**10操作是否针对列表推导的每次迭代而不是整个总和进行了优化？
$ time python pe48.py
9110846700
real 0m0.070s
user 0m0.047s
sys 0m0.015s
鉴于
print sum([i**i for i in range(1,1001)])%(10**10)
和
print sum([i**i for i in range(1,1001)])
在 Python 中功能同样快，你最后一个问题的答案是“不”。
因此，Python 必须能够非常快速地进行整数求幂。碰巧整数幂是 O(log(n)) 乘法：http ://en.wikipedia.org/wiki/Exponentiation#Efficient_computation_of_integer_powers
基本上所做的是，你意识到 2^100 也是 2^64 * 2^32 * 2^4 ，而不是做 2^100 = 2*2*2*2*2... 100 次，你可以一遍又一遍地平方 2 得到 2^2 然后 2^4 然后 2^8... 等等，一旦你找到了所有这三个分量的值，你就可以将它们相乘以获得最终答案。这需要更少的乘法运算。具体如何实现它有点复杂，但是 Python 已经足够成熟，可以在这样一个核心特性上进行很好的优化。
不，它适用于整个金额。总和本身的计算速度非常快。如果参数是整数，那么做指数并不难。