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?
Input
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).
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.
Solve
对于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
Code
/************************************************************************* > 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;
}
