ACM 10162 Last Digit

這題的N值高達2*10^100，如果直接暴力解一定會Time Limit Exceeded

一開始看到這題應該會想到其實只要將每個數字的個位數加起來就可以了，不需要硬算類似132^132這種超大的數字。不過這個想法還不太夠，因為N值實在太大了。我們現在來看一下13^13這個數字：
仔細觀察會發現其實13^13和3^13的個位數其實是相同的，再加上其實3^1, 3^2, 3^3, 3^4, 3^5, 3^6, 3^7....的個位數其實是有規律的，這個規律是以3, 9, 7, 1一直重複下去，所以3^13的個位數其實就是3，也就是13^13的個位數其實就是3

現在我們再來看23^23這個數字，觀察後會發現23^23和3^23的個位數其實是相同的，因為有3, 9, 7, 1這個規律，我們可以很快推得3^23的個位數是7，也就是23^23的個位數其實就是7

接著再來看33^33和43^43這兩個數字，你會發現個位數分別是3和7，再來看53^53和63^63，你會觀察到一件事：
(1) 個位數是3的有13^13, 33^33, 53^53... 也就是如果底的最末位是3，而且只要次方的十位數是奇數，那麼個位數就是3。像53^53的次方的十位數是5，是個奇數，所以個位數是3
(2) 個位數是7的有23^23, 43^43, 63^63... 也就是如果底的最末位是3，而且只要次方的十位數是偶數，那麼個位數就是7。像43^43的次方的十位數是4，是個偶數，所以個位數是7

再來請用相同的方法觀察2^2, 12^12, 22^22, 32^32, 42^42，你會發現底的最末位為2的數字竟然也存在著這種規律。分析完底的最末位分別為0, 1, 2, 3, 4, 5, 6, 7, 8, 9的數字以後，可以整理出下表：

底的最末位	次方的十位數為偶數	次方的十位數為奇數
0	0	0
1	1	1
2	4	6
3	7	3
4	6	6
5	5	5
6	6	6
7	3	7
8	6	4
9	9	9

現在我們來看如果今天N=32的話，該怎麼計算會比較快
因為N=32, 所以S = 1^1 + 2^2 + 3^3 + ... + 32^32
利用上表，我們可以直接得出結果是：
(0 + 1 + 4 + 7 + 6 + 5 + 6 + 3 + 6 + 9) + (0 + 1 + 6 + 3 + 6 + 5 + 6 + 7 + 4 + 9) + (0 + 1 + 4 + 7 + 6 + 5 + 6 + 3 + 6 + 9) + (0 + 1 + 6)
= 47 * 3 + (0 + 1 + 6)
多試試幾個不同的N值，你就會推出一個公式，可以很快就算出來題目的要求。推出公式後要注意的是題目的N值很大！

下面第一份code只能處理N <= INT_MAX的情況，不過我覺得這份code比較好容易理解
第二份code則是能處理N <= 2*10^100的情況


#1
#include <stdio.h>

int table[2][10] = {
    {0, 1, 4, 7, 6, 5, 6, 3, 6, 9},
    {0, 1, 6, 3, 6, 5, 6, 7, 4, 9}
};

int main(void)
{
    int i, n, result;
    char s[101+1];

    while (scanf("%d", &n) == 1 && n) {
        result = (n / 10) * 47;
        for (i = 1; i <= n%10; ++i)
            result += table[(n/10)%2][i];

        printf("%d\n", result % 10);
    }

    return 0;
}


#2
#include <stdio.h>
#include <string.h>

int table[2][10] = {
    {0, 1, 4, 7, 6, 5, 6, 3, 6, 9},
    {0, 1, 6, 3, 6, 5, 6, 7, 4, 9}
};

int main(void)
{
    int i, result, tens, len;
    char s[101+1];

    while (scanf("%s", s) == 1 && !(s[0] == '0' && s[1] == '\0')) {
        len = strlen(s);

        if (len >= 2)
            tens = s[len-2] - '0';
        else
            tens = 0;

        result = tens * 7;
        for (i = 1; i <= s[len-1]-'0'; ++i)
            result += table[tens%2][i];

        printf("%d\n", result % 10);
    }

    return 0;
}