首页 > 代码库 > 2014 Super Training #4 G What day is that day? --两种方法
2014 Super Training #4 G What day is that day? --两种方法
原题： ZOJ 3785 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3785
题意：当天是星期六，问经过1^1+2^2+3^3....+n^n天后是星期几？
这题开始以为是这种式子的求和问题，翻了半天没翻到公式。结果没搞出来。后来发现有两种方法。
第一种方法： 找规律
打表可以看出，这些数的结果出现42一循环，所以直接就处理出前42个，后面的就用前面的。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>using namespace std;#define N 20007int sum[44];string ss[8] = {"Saturday","Sunday","Monday","Tuesday","Wednesday","Thursday","Friday"};void init(){ int n,i,j; sum[0] = 0; for(n=1;n<=44;n++) { int flag = n%7; int ans = 1; for(j=1;j<=n;j++) ans = (ans*flag)%7; sum[n] = ans; } for(i=1;i<=44;i++) sum[i] += sum[i-1];}int main(){ int i,j,t,n,ans; init(); scanf("%d",&t); while(t--) { scanf("%d",&n); ans = (((n/42)%7*(sum[42]%7))%7 + sum[n%42]%7)%7; cout<<ss[ans]<<endl; } return 0;}
第二种方法： 矩阵乘法
有待更新
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。