ZOJ 3785 What day is that day?（数论：费马小定理）

What day is that day?

---

Time Limit: 2 Seconds      Memory Limit: 65536 KB

---

It's Saturday today, what day is it after 11 + 22 + 33 + ... + NN 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.

分析：运用费马小定理 ，简化运算并求出循环节

1^1     2^2     3^3     4^4     5^5     6^6     7^7

8^8     9^9     10^10   11^11   12^12   13^13   14^14

15^15   16^16   17^17   18^18   19^19   20^20   21^21

22^22   23^23   24^24   25^25   26^26   27^27   28^28

29^29   30^30   31^31   32^32   33^33   34^34   35^35

36^36   37^37   38^38   39^39   40^40   41^41   42^42

43^43   44^44   45^45   46^46   47^47   48^48   49^49

转化后-->>

1^1     2^2     3^3      4^4     5^5     6^6      0

1^2     2^3     3^4      4^5     5^6     6^1      0

1^3     2^4     3^5      4^6     5^1     6^2      0

1^4     2^5     3^6      4^1     5^2     6^3      0

1^5     2^6     3^1      4^2     5^3     6^4      0

1^6     2^1     3^2      4^3     5^4     6^5      0

1^1     2^2     3^3      4^4     5^5     6^6      0

#include<iostream>

#include<math.h>

#define ll long long

using namespace std;

int s[50];

void chose(ll x){

        switch(x){

                case 0:printf("Sunday\n");break;

                case 1:printf("Monday\n");break;

                case 2:printf("Tuesday\n");break;

                case 3:printf("Wednesday\n");break;

                case 4:printf("Thursday\n");break;

                case 5:printf("Friday\n");break;

                case 6:printf("Saturday\n");break;

        }

}

int main()

{

        int T;

        ll n;

        for(int i=1;i<=42;i++){

                int a,p,sum=1;

                p=(i%6)?i%6:6;

                //为6的倍数情况下保留一个六

                a=i%7;

                for(int j=1;j<=p;j++)

                        sum=(sum*a)%7;

                s[i]=(s[i-1]+sum)%7;

        }

        scanf("%d", &T);

        while(T--){

                scanf("%lld", &n);

                ll ans=(n/42%7*s[42]%7+s[n%42])%7;

                ans=(ans+6)%7;

                chose(ans);

        }

        return 0;

}