ZOJ 3785 What day is that day? 循环节找规律

题意：求给定式子%7的结果

暴力求循环节发现 f[1] = f[295], f[2] = f[296]······

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <math.h>
#include <set>
#include <vector>
#include <queue>
using namespace std;
#define N 10000
#define ll long long
ll n, m;
#define J 1000
ll f[N];
void put(ll x){
	if(x==1)puts("Sunday");
	if(x==2)puts("Monday");
	if(x==3)puts("Tuesday");
	if(x==4)puts("Wednesday");
	if(x==5)puts("Thursday");
	if(x==6)puts("Friday");
	if(x==0)puts("Saturday");
}
ll quick_pow(ll x, ll y){
	ll ans = 1;
	while(y){
		if(y&1)ans = (ans*x)%7;
		y >>= 1;
		x = (x*x)%7;
	}
	return ans;
}
int main(){		
	ll i, j;
	f[1] = 1;
	for(i = 2; i < N; i++)f[i] = (f[i-1]+quick_pow(i,i))%7;
	f[0] = f[294];
	/*for(i = J+1; i < N; i++){
		bool yes = true;
		for(j = 1; j <= J; j++)
			if(f[j]!=f[j+i-1]){yes = false;break;}

		if(yes)
			printf("从第%lld个开始和前J个相同\n",i);
	}*/
	ll T;scanf("%lld",&T);
	while(T--){
		scanf("%lld",&i);
		put(f[i%294]);
	}
	return 0;
}

ZOJ 3785 What day is that day? 循环节找规律,布布扣,bubuko.com

ZOJ 3785 What day is that day? 循环节找规律

原文：http://blog.csdn.net/acmmmm/article/details/23677015