【欧拉计划】48. Self powers

（本题取 $n=1000$，$m=10^{10}$)

【思路】Python 直接套 pow：

mod = int(1e10)
ans = 0
for i in range(1, 1001): ans = (ans + pow(i, i, mod)) % mod
print(ans)

也可以使用快速幂+龟速乘，时间复杂度为 $\mathcal O(n \log n \log m)$。当然快速乘可优化到 $\mathcal O(n \log n)$：

#include<stdio.h>
const long long mod=1e10;
long long ans;
long long mul(long long a,long long b)
{
    long long s=0;
    while(b)
    {
        if(b&1)s=(s+a)%mod;
        a=(a<<1)%mod;
        b>>=1;
    }
    return s;
}
long long power(long long a,long long b)
{
    long long s=1;
    while(b)
    {
        if(b&1)s=mul(s,a)%mod;
        a=mul(a,a)%mod;
        b>>=1;
    }
    return s;
}
int main()
{
    for(int i=1;i<=1000;++i)ans+=power(i,i);
    printf("%lld",ans%mod);
    return 0;
}