ZOJ-3785 What day is that day?

2023-12-26 05:32

文章标签 day zoj 3785

本文主要是介绍ZOJ-3785 What day is that day?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题意：
今天是星期六，求1^1 + 2^2 + 3^3 + … + N^N 天以后是星期几。计算这个数字对7取模，用余数判断是周几。
用到快速幂。
但是如果每一个输入都一个一个求，数字太大肯定会超时。
而且，这个题，输入的数据很多，用cout、cin也会超时。
必须用 scanf和printf。
试着输出对前一百个数，n^n%7 以后，发现有规律，42个数字一组。
所以对于n，对42取模以后再计算。

最开始想错了，以为，增加的余数有规律，然后以为mod42余数相同的N的结果是一样的，WA了很久。
根据输出，mod42余数为41的数字，n^n%7结果是6，那么，n每增加42，他mod7的结果要比42个数字前的那个书mod7的结果多6.
所以，应该是对输入的N除以7处理，然后往上加6，再往后继续数n%7个数，看余数。
例如 n=173时
n/42=4 n%4=5
5%7=5
那么余数就是 res=4*6+=29
此时再对res%7=1
那么这一天是周日。

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#define Max 100
using namespace std;int a[Max];long long f(long long a, long long p, long long m)//快速幂
{long long res = 1, t;long long k = p;t = a%m;while (k){if (k % 2 == 1)res = res*t%m;t = t*t%m;k /= 2;}return res;
}void d()
{int i;for (i = 1, a[0] = 0; i < Max; i++)//前100个数mod7的结果保存，其实42个就够了a[i] = (f(i, i, 7) + a[i - 1]) % 7;
}int main()
{d();long long T;long long i, j, k, t;long long tmp;long long sum;while (cin >> T){for (j = 0; j < T; j++){scanf("%I64d",&tmp);t = tmp / 42;tmp %= 42;sum = (a[tmp]+6*t)%7;//简化余数switch (sum){case 1:printf("Sunday\n"); break;case 2:printf("Monday\n"); break;case 3:printf("Tuesday\n"); break;case 4:printf("Wednesday\n"); break;case 5:printf("Thursday\n"); break;case 6:printf("Friday\n"); break;case 0:printf("Saturday\n"); break;}}}return 0;
}