UVa 10162 Last Digit：数学规律

UVa 10162 Last Digit：数学规律2014-07-07 synapse7 http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=11031. 先看单个数的规律：

0^n%10: 0

1^n%10: 1

2^n%10: 2,4,8,6

3^n%10: 3,9,7,1

4^n%10: 4,6

5^n%10: 5

6^n%10: 6

7^n%10: 7,9,3,1

8^n%10: 8,4,2,6

9^n%10: 9,1

2. 因为最大循环长度为4，所以我们可以看到，i^i%10和i^（i+20）%10是相同的，也就是说，i^i%10的周期是20

而（1^1+……+20^20）%10=4，

所以（1^1+……+40^40）%10=8，

（1^1+……+60^60）%10=2，（1^1+……+80^80）%10=6，（1^1+……+100^100）%10=0，这么看来，S（N）%10=S（N%100）%10

所以考虑N的后两位即可。

3. 为了简化运算，还可以进一步分析：

不妨算一算（1^1+……+10^10）%10=7，所以（11^11+……+20^20）%10=7（上面得出的4-7+10=7），所以每十个数的和模10余7，

那么我们算出S（1）~S（10）的个位及[S（11）-S（10）]~[S（20）-S（10）]的个位a[i]后，

记b=N%100，则ans=（b/10*7+a[b%20]）%10

完整代码：

01./*0.015s*/02.03.#include<bits/stdc++.h>04.using namespace std;05.const int a[20] = {0, 1, 5, 2, 8, 3, 9, 2, 8, 7, 0, 1, 7, 0, 6, 1, 7, 4, 8, 7}; ///S（N）%10,0<=N<=1906.07.char s[105];08.09.int main（）10.{11.int len, b, c;12.while （gets（s）, s[0] ！= "0"）13.{14.len = strlen（s）;15.if （len == 1） b = s[0] & 15;16.else b = atoi（s + len - 2）;17.printf（"%d
", （b / 10 * 7 + a[b % 20]） % 10）;18.}19.return 0;20.}