UVA10162

點我進UVA10162

題意:

輸入N值，帶入公式
S = 1^1 + 2^2 + 3^3 + . . . + N^N
找出S的最後一個digit值

解題思路:

由於這數字範圍太大，所以只能用字串來解。
可以找到規律，發現尾數每20個循環一次，且下一個循環會比上一次加4，整個循環為100個
如下:
0，1，5，2，8，3，9，2，8，7，7，8，4，7，3，8，4，1，5，4，
4，5，9，6，2，7，3，6，2，1，1，2，8，1，7，2，8，5，9，8，
8，9，3，0，6，1，7，0，6，5，5，6，2，5，1，6，2，9，3，2，
2，3，7，4，0，5，1，4，0，9，9，0，6，9，5，0，6，3，7，6，
6，7，1，8，4，9，5，8，4，3，3，4，0，3，9，4，0，7，1，0，
所以要取出N的最後兩個digits，計算這兩個(digits%20+4*這兩個digits/20)%10

參考連結:https://blog.csdn.net/mobius_strip/article/details/37757287

#include <bits/stdc++.h>

using namespace std;
 
int t[20] = {0,1,5,2,8,3,9,2,8,7,7,8,4,7,3,8,4,1,5,4};//先建立第一個循環的20個尾數值列表
 
int main()
{
string s;//由於數字範圍太大所以用字串來算
while(cin>>s){
int l=s.length();
if(l==1&&s[0]=='0')break;
int a=s[l-1]-'0';//將input的最後一個digit轉成int
if(l>1)a+=(s[l-2]-'0')*10;//將input的倒數第二個digit轉成int，所以現在a等於input的最後兩位
cout<<(t[a%20]+a/20*4)%10<<endl;
}
return 0;
}