Time Limit: 2 Seconds Memory Limit: 65536 KB
It’s Saturday today, what day is it after $1^1 + 2^2 + 3^3 + … + N^N$ days?
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
There is only one line containing one integer N (1 <= N <= 1000000000).
Output
For each test case, output one string indicating the day of week.
Sample Input
2
1
2
Sample Output
Sunday
Thursday
Hint
A week consists of Sunday, Monday, Tuesday, Wednesday, Thursday, Friday and Saturday.

思路
要算出最后是星期几，只要把天数模7就能得到增长了的星期数，从而换算出具体星期。计算式子：
$$(1^1+2^2+3^3+…+N^N)\%7=$$$$1^1\%7+2^2\%7+3^3\%7+…+N^N\%7$$
当 a>=7 时，
$a\%7=0$，有$a^a\%7=0$，即$7^7\%7=0,14^{14}\%7=0$;
$a\%7\neq0,a>7$，根据二项式定理：
$$(a+b)^n=C_n^0a^n+C_n^1a^{n-1}b+…+C_n^{n-1}a^1b^{n-1}+C_n^nb^n$$所以有：$a^n\%7=(7+a-7)^n\%7=(a-7)^n$，如：$9^9\%7=2^9$
根据这个规律有：$$
\begin{array}{|c|c|}
\hline a^a & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline 1 & 1^1 & 2^2 & 3^3 & 4^4 & 5^5 & 6^6 & 0 \\
\hline 2 & 1^8 & 2^9 & 3^{10} & 4^{11} & 5^{12} & 6^{13} & 0 \\
\hline 3 & 1^{15} & 2^{16} & 3^{17} & 4^{18} & 5^{19} & 6^{20} & 0 \\
\hline 4 & 1^{22} & 2^{23} & 3^{24} & 4^{25} & 5^{26} & 6^{27} & 0 \\
\hline 5 & 1^{29} & 2^{30} & 3^{31} & 4^{32} & 5^{33} & 6^{34} & 0 \\
\hline 6 & 1^{36} & 2^{37} & 3^{38} & 4^{39} & 5^{40} & 6^{41} & 0 \\
\hline
\end{array}
$$又根据费马小定理：$a^n=a(mod n)$，得：$a^7=a(mod 7)$；所以有：$$
\begin{array}{|c|c|}
\hline a^a & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline 1 & 1^1 & 2^2 & 3^3 & 4^4 & 5^5 & 6^6 & 0 \\
\hline 2 & 1^2 & 2^3 & 3^4 & 4^5 & 5^6 & 6^7 & 0 \\
\hline 3 & 1^3 & 2^4 & 3^5 & 4^6 & 5^7 & 6^8 & 0 \\
\hline 4 & 1^4 & 2^5 & 3^6 & 4^7 & 5^8 & 6^9 & 0 \\
\hline 5 & 1^5 & 2^6 & 3^7 & 4^8 & 5^9 & 6^{10} & 0 \\
\hline 6 & 1^6 & 2^7 & 3^8 & 4^9 & 5^{10} & 6^{11} & 0 \\
\hline
\end{array} $$表格中第二列说明了6层1循环，循环节是42。接下来是模运算，先计算第一层，后面逐层对上一层结果乘底数取模即可：$$
\begin{array}{|c|c|}
\hline a^a\%7 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline 1 & 1 & 4 & 6 & 4 & 3 & 1 & 0 \\
\hline 2 & 1 & 1 & 4 & 2 & 1 & 6 & 0 \\
\hline 3 & 1 & 2 & 5 & 1 & 5 & 1 & 0 \\
\hline 4 & 1 & 4 & 1 & 4 & 4 & 6 & 0 \\
\hline 5 & 1 & 1 & 3 & 2 & 6 & 1 & 0 \\
\hline 6 & 1 & 2 & 2 & 1 & 2 & 6 & 0 \\
\hline
\end{array} $$
然后从 a=2 开始做加法，接着再从a=43开始，把上一个循环节的尾部元素与第一个循环节的对应位置元素依次相加。观察到第一个循环节的尾部元素为6，第二个为5，…第七个为0，故最终的取和循环节长度为42*7=294。通过打表输出这些数字，得到代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<stdio.h> 
char day[294] = {
1,5,4,1,4,5,5,
6,0,4,6,0,6,6,
0,2,0,1,6,0,0,
1,5,6,3,0,6,6,
0,1,4,6,5,6,6,
0,2,4,5,0,6,6,
0,4,3,0,3,4,4,
5,6,3,5,6,5,5,
6,1,6,0,5,6,6,
0,4,5,2,6,5,5,
6,0,3,5,4,5,5,
6,1,3,4,6,5,5,
6,3,2,6,2,3,3,
4,5,2,4,5,4,4,
5,0,5,6,4,5,5,
6,3,4,1,5,4,4,
5,6,2,4,3,4,4,
5,0,2,3,5,4,4,
5,2,1,5,1,2,2,
3,4,1,3,4,3,3,
4,6,4,5,3,4,4,
5,2,3,0,4,3,3,
4,5,1,3,2,3,3,
4,6,1,2,4,3,3,
4,1,0,4,0,1,1,
2,3,0,2,3,2,2,
3,5,3,4,2,3,3,
4,1,2,6,3,2,2,
3,4,0,2,1,2,2,
3,5,0,1,3,2,2,
3,0,6,3,6,0,0,
1,2,6,1,2,1,1,
2,4,2,3,1,2,2,
3,0,1,5,2,1,1,
2,3,6,1,0,1,1,
2,4,6,0,2,1,1,
2,6,5,2,5,6,6,
0,1,5,0,1,0,0,
1,3,1,2,0,1,1,
2,6,0,4,1,0,0,
1,2,5,0,6,0,0,
1,3,5,6,1,0,0
};
int main()
{
    int i,t;
    int a;
    char str[7][10]={"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday","Thursday", "Friday"};   
    scanf("%d",&t);
    for(i=0; i<t; i++){
        scanf("%d",&a);
        printf("%s\n",str[day[(a-1)%294]]);
    }
    return 0;
}

注意：这段C代码可以AC，但是改成C++风格的输入输出就会报”Time Limit Exceeded”,Run Time(ms)为2001ms，正好超了1ms。
网上还找了一段可以AC的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>  
int s[45];  
char str[7][10]={"Saturday","Sunday","Monday","Tuesday","Wednesday","Thursday","Friday"};  
int main()  
{  
    s[0]=0;  
    for(int i=1;i<=44;i++)  
    {  
        int flag=i%7;  
        int ans=1;  
        for(int j=1;j<=i;j++)  
            ans=(ans*flag)%7; //每乘一次就取模一次 
        s[i]=ans;  
    }  
    for(int i=1;i<=44;i++)  
        s[i]+=s[i-1];  
    int t;  
    scanf("%d",&t); 
    while(t--)  
    {  
        int n;  
        scanf("%d",&n);  
        int ans=(n/42%7*(s[42]%7)%7+s[n%42]%7)%7; // 
        printf("%s\n",str[ans]);  
    }  
}

参考资料：
Simon_X ZOJ 3785 What day is that day?(今天是星期几？)
sdjzping的专栏 ZOJ 3785 What day is that day? （找规律）