Problem
题目大意：
求 (1^1+2^2+3^3+cdots+n^n) 的最后一位。其中 (1 le n le 2 imes 10^{100})。
Solution
其实是个简单的找规律题 QwQ。
我们不妨设 (S(k)=sumlimits_{i=1}^k i^i)。那么答案就是 (S(n))。
先给出结论：(S(k)=S(k mod 100))。
首先，我们可以通过打表或在 uDebug 上输数据发现，(S(100)=0)。
然后，对于每一个大于 (100) 的数 (k)，我们可以将其表示为 (100a+b) 的形式。题目求最后一位，其实就是对 (10) 取模。
那么：
[k^k=(100a+b)^{100a+b} equiv b^{100a+b} pmod{10}
]
同样的道理，我们也可以对 (b) 拆解，设 (b=10c+d)，那么：
[b^{100a+b} equiv b^{(100a+b) mod 4 + 4} equiv (10c+d)^{d+4} equiv d^{d+4} equiv d^{(d+4) mod 4+4} equiv d^d pmod{10}
]
又因为是在模 (10) 意义下，也就是取个位，所以 (k^k equiv d^d equiv b^b pmod{10})。
所以我们只要预处理出 (S(0),S(1),S(2),cdots,S(99))，然后对于每次读入取末两位即可。
Code
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[100];
string n;
int power(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans=ans*a%10;
a=a*a%10;
b>>=1;
}
return ans%10;
}
int main()
{
for(int i=1;i<100;i++) a[i]=(a[i-1]+power(i,i))%10;
while(cin>>n&&n!="0")
if(n.length()<2) printf("%d
",a[(n[0]-'0')]);
else printf("%d
",a[(n[n.length()-2]-'0')*10+n[n.length()-1]-'0']);
return 0;
}