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+…+NN1^1 + 2^2 + 3^3 + … + N^N11+22+33+…+NN days?

There are multiple test cases. The first line of input contains an integer TTT indicating the number of test cases. For each test case:

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

For each test case, output one string indicating the day of week.

2
1
2


Sunday
Thursday

A week consists of Sunday, Monday, Tuesday, Wednesday, Thursday, Friday and Saturday.

对于1…N1 \dots N1…N，对于777取模后，可以转换成一大串0…60 \dots 60…6的循环，所以11+22+33+…+NN1^1 + 2^2 + 3^3 + … + N^N11+22+33+…+NN可以转换成：11+22+33+…(N%7)N1^1+2^2+3^3+ \dots (N\%7)^N11+22+33+…(N%7)N，然后我们可以发现，这个式子的值是七个等比数列的前xxx项和的总和。每项公比为num7num^7num7，第一项为nnn^nnn(0≤n≤6)(0\leq n \leq 6)(0≤n≤6)

那么我们只需要统计出0…60\dots 60…6的个数，并利用等比数列的前nnn项和公式计算即可

百度了一下，发现似乎写麻烦了，貌似可以直接打表找规律？而且代码还特别短，想看短代码的自行百度吧，貌似没有找到我这种方法写的QAQ

/*************************************************************************

     > Author: WZY
     > School: HPU
     > Created Time:   2019-04-20 09:49:05

************************************************************************/
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
const int inf=(1<<30);
const ll INF=(1LL*1<<60);
const int maxn=1e6+10;
const int mod=1e9+7;
const int maxm=1e3+10;
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1;y=0;
        return a;
    }
    else
    {
        int r=exgcd(b,a%b,y,x);
        y-=x*(a/b);
        return r;
    }
}
int inv(int a,int n)
{
    int x,y;
    exgcd(a,n,x,y);
    x=(x%n+n)%n;
    return x;
}
int Pow(int a,int b,int c)
{
    int res=1;
    while(b)
    {
        if(b&1)
            res=res*a%c;
        a=a*a%c;
        b>>=1;
    }
    return res;
}
int a[10];
int sum[10];
int main(int argc, char const *argv[])
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    // 计算第一项的值
    for(int i=1;i<7;i++)
        sum[i]=Pow(i,7,7);
    cin>>t;
    int n;
    while(t--)
    {
        ms(a,0);
        cin>>n;
        // 统计0~6出现的个数
        for(register int i=1;i<7;i++)
            a[i]=n/7+(n%7>=i);
        // 0忽略，初始值为1的个数
        int ans=a[1];
        int __=0;
        for(register int i=2;i<7;i++)
        {
            // 利用前n项和公式+逆元计算对7取模的结果
            int _=(Pow(i,i,7)*((Pow(sum[i],a[i],7)-1+7)%7)*inv(sum[i]-1,7)+7)%7;
            __+=_;
            if(a[i]==0)
                break;
        }
        ans=(ans+__)%7;
        int cnt=(6+ans)%7;
        if(cnt==0)
            cout<<"Sunday\n";
        if(cnt==1)
            cout<<"Monday\n";
        if(cnt==2)
            cout<<"Tuesday\n";
        if(cnt==3)
            cout<<"Wednesday\n";
        if(cnt==4)
            cout<<"Thursday\n";
        if(cnt==5)
            cout<<"Friday\n";
        if(cnt==6)
            cout<<"Saturday\n";
    }
    return 0;
}