# 计算日期（快速幂+打表） - ZOJ 3785

It's Saturday today, what day is it after11 + 22 + 33 + ... + NN days?

Input

There are multiple test cases. The firstline of input contains an integer T indicating the number of test cases. Foreach test case:

There is only one line containing oneinteger N (1 <= N <= 1000000000).

Output

For each test case, output one stringindicating 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.

1.先用快速幂求出11 ， 22 +，33 ， ... ，NN

(1^1)%7=(43^43)%7,

(2^2)%7=(44^44)%7,

(3^3)%7=(45^45)%7,

(n^n)%7=( (42+n)^(42+n) )%7

```#include<bits/stdc++.h>
using namespace std;

int fast_pow(int a, int n, int mod)
{
int ret = 1;

while (n)
{
if (n & 1)
ret = ret * a % mod;

a = a * a % mod;
n >>= 1;
}

return ret;
}

int main()
{

for (int i = 1; i <= 1000; i++)
{
printf("%d,", fast_pow(i, i, 7));

if (i % 7 == 0)
printf("\n");
}

return 0;

}```

//以42为一组

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

1,4,6,4,3,1,0,

1,1,4,2,1,6,0,

1,2,5,1,5,1,0,

1,4,1,4,4,6,0,

1,1,3,2,6,1,0,

1,2,2,1,2,6,0,

2.然后打表求出[1,42]区间每个数n的(n^n)%7,再求a数组的前缀和b数组，

sum表示一个循环节所贡献的天数，即sum=（1^1+2^2+3^3+......+41^41+41^42）%7=6;

AC代码：C++

```#include<bits/stdc++.h>

using namespace std;

chars[10][10] = {"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};

int fast_pow(int a, int n, int mod) //快速幂取模
{
int ret = 1;

while (n) {
if (n & 1)
ret = ret * a % mod;
a = a * a % mod;
n >>= 1;
}

return ret;
}

int a[50];//a[n]表示(n^n)%7
int b[50];//b[n]表示a[1]+a[2]+....+a[n]

int main()
{
ios::sync_with_stdio(0);
b[0] = 0;

for (int i = 1; i <= 42; i++) //循环节为42
{
a[i] = fast_pow(i, i, 7);
b[i] = b[i - 1] + a[i];
}

int t;

cin >> t;

while (t--) {
int n;
cin >> n;
int sum = b[42] % 7; //一个循环节贡献的天数
int num = n / 42; //循环节的个数
int ans = (sum * num % 7 + b[n % 42] % 7) % 7;
printf("%s\n", s[ans]);
}

return 0;

}```

```#include<bits/stdc++.h>
using namespace std;

chars[10][10] = {"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};

int fast_pow(int a, int n, int mod) //快速幂取模
{
int ret = 1;

while (n) {
if (n & 1)
ret = ret * a % mod;
a = a * a % mod;
n >>= 1;
}

return ret;
}

int a[50];//a[n]表示(n^n)%7
int b[50];//b[n]表示a[1]+a[2]+....+a[n]

int main()
{
ios::sync_with_stdio(0);
b[0] = 0;
int sum = 0;

for (int i = 1; i <= 42; i++) //循环节为42
{
a[i] = fast_pow(i, i, 7);
b[i] = b[i - 1] + a[i];
sum = (sum % 7 + a[i] % 7) % 7; //重点理解
}

int t;
cin >> t;

while (t--) {
int n;
cin >> n;
int ans = (sum * (n / 42) % 7 + b[n % 42] % 7) % 7;
printf("%s\n", s[ans]);
}

return 0;
}```

216 篇文章34 人订阅

0 条评论

## 相关文章

47380

### leetcode打家劫舍问题

https://leetcode-cn.com/problems/house-robber/description/

19720

### 一文盘点三大顶级Python库（附代码）

Python在许多方面有着强大的吸引力 - 例如效率、代码可读性和速度方面，也正因为如此，对于希望提升应用程序功能的数据科学家和机器学习专家来说，Python通...

21340

### 洛谷讲课手稿

Hello大家好，我是洛谷的HansBug。首先自我介绍下，我现在在北京航空航天大学，计算机科学与技术专业读大二，我参加过2013-2015年的提高组NOIP和...

32740

58790

90870

### MongoDB的数据建模

MongoDB是一种面向Document的NoSQL数据库，如果我们还是按照RDB的方式来思考MongoDB的数据建模，则不能有效地利用MongoDB的优势；然...

35660

### 1022: [SHOI2008]小约翰的游戏John【Nim博弈，新生必做的水题】

1022: [SHOI2008]小约翰的游戏John Time Limit: 1 Sec  Memory Limit: 162 MB Submit: 2709 ...

33180

38370

24620