用最直接的方式计算$n^{15}$需要作14次乘法： $$n\times n\times\ldots\times n=n^{15}.$$ 若使用二分法分治，则可以只作6次乘法： \begin{align*} n\times n&=n^2 \\ n^2\times n^2&=n^4 \\ n^4\times n^4&=n^8 \\ n^8\times n^4\times n^2\times n&=n^{15} \end{align*} 若用更巧妙一些的方式设计分治策略，也可以只作5次乘法： \begin{align*} n\times n&=n^2 \\ n^2\times n&=n^3 \\ n^3\times n^3&=n^6 \\ n^6\times n^6\times n^3&=n^{15} \end{align*} 这也是可能的最少乘法次数。

记$m(k)$为计算$n^k$所需要的最少乘法次数，例如$m(15)=5$，求$\sum\limits_{k=1}^{200}m(k)$。

本题难度:

解答

若数列$a_1,\ldots, a_r$严格递增，满足$a_1=1$、 $a_i=a_j+a_k$ ($i>j\ge k$)，且$a_1+\ldots+a_r=k$，那么$a_1,\ldots, a_r$就对应了一种分治策略，这样的数列称为k的加法链(addition chain of k)。

根据题意，对每个给定的k，需要找到最小的r，该值已在OEIS A003313中给出，前10万个k所对应的最短r在该文件中，结果是$1582$。

d=[]
with open("122_chain.txt") as f:
    for line in f:
        d.append(int(line.split()[1]))
print sum(d[:200])