|
Description |
题目描述 |
|
It’s Saturday today, what day is it after 11 + 22 + 33 + … + NN days? |
今天是星期六，11 + 22 + 33 + … + NN 天后是星期几？ |
|
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). |
多组测试样例。 输入的首行是一个整数T表示测试样例的数量。每个测试样例包含： 只有一行，且每行只有一个整数N (1 <= N <= 1000000000)。 |
|
Output |
输出 |
|
For each test case, output one string indicating the day of week. |
每个测试样例输出一个字符串表示星期几。 |
|
Sample Input – 输入样例 |
Sample Output – 输出样例 |
|
2 1 2 |
Sunday Thursday |
|
Hint |
提示 |
|
A week consists of Sunday, Monday, Tuesday, Wednesday, Thursday, Friday and Saturday. |
一周中包含Sunday, Monday, Tuesday, Wednesday, Thursday, Friday and Saturday。 |
【题解】
想算出最后是星期几，只要把天数模7就能得到增长了的星期数，从而换算出具体星期。
因此我们需要计算的式子可表示为：
(11+ 22+ 33+…+ NN)%7
11%7+ 22%7+ 33%7+…+ NN%7
然后对于大等于7的数，aN%7可以得到：
7N%7 = (7%7)N%7 = 0N，8N%7 = (8%7)N%7 = 1N，…………以此类推
后继的元素全部遵循这个规律，因此所求a的值为[ 0, 6]。
对于aN%7，a属于[ 0, 6]：
|
元素\次方%7 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
0 |
0%7已经为0，其结果全部为0 |
||||||
|
1 |
1 |
1……出现循环 |
|||||
|
2 |
1 |
2 |
4 |
1……出现循环 |
|||
|
3 |
1 |
3 |
2 |
6 |
4 |
5 |
1……出现循环 |
|
4 |
1 |
4 |
2 |
1……出现循环 |
|||
|
5 |
1 |
5 |
4 |
6 |
2 |
3 |
1……出现循环 |
|
6 |
1 |
6 |
1……出现循环 |
||||
所求式子可展开为：
|
第一层 |
11 |
22 |
33 |
44 |
55 |
66 |
07 |
|
第二层 |
18 |
29 |
310 |
411 |
512 |
613 |
014 |
|
第三层 |
115 |
216 |
317 |
418 |
519 |
620 |
021 |
|
第四层 |
122 |
223 |
324 |
425 |
526 |
627 |
028 |
|
第五层 |
129 |
230 |
331 |
432 |
533 |
634 |
035 |
|
第六层 |
136 |
237 |
338 |
439 |
540 |
641 |
042 |
|
第七层 |
…………………………………………………… |
||||||
然后把每层加起来再%7，可以得到长度为6*7 = 42的循环节。
然后根据每层的循环节套上每个元素的循环节，得到最终循环节，长度为42*7 = 294
附：原本想比较科学地证明最终循环节的长度是294，最后发现坑越挖越大，然后以现在的渣水平填不上，就弃了……
【代码 C++】
#include<cstdio>
int day[] = {
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , , ,
};
char opt[][] = {
"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"
};
int main(){
int t, a;
scanf("%d", &t);
while (t--){
scanf("%d", &a);
puts(opt[day[a % ]]);
}
return ;
}
ZOJ 3785
