【題目鏈接】

ybt 1083：計算星期幾
OpenJudge NOI 小學奧數 7831:計算星期幾

【題目考點】

1. 同余定理

根據同余定理，有：
$(a?b)\%m=(a\%m?b\%m)\%m$

2. 冪取模

$\begin{array}{rl}{a}^b\%m& =(a^{b?1}?a)\%m\\ & =(a^{b?1}\%m?a\%m)\%m\end{array}$
這就是求$a^b\%m$的遞推公式
其中b = 1時$a^b\%m=a\%m$

3.選擇輸出字符串時，可以用switch語句。也可以將各星期的字符串存入二維字符數組（或string類數組）中，用下標索引。

【解題思路】

1. 遞推

設v[i]表示$a^b\%m$
有：
v[i] = (v[i-1] * a%m) %m;
v[1] = a % m;

2. 迭代

迭代法思路與遞推相似，只不過不用數組，只用變量。每次求出的值都賦值給變量s。
初始值：s = a % m;
循環中：s = (s * (a % m)) % m;

3. 遞歸

函數設為：
int solve(int b);求$a^b\%m$的值
要求該值，需要先求$a^{b?1}\%m$的值，而后代入公式$a^b\%m=(a^{b?1}\%m?a\%m)\%m$

【題解代碼】

解法1：迭代法，用switch語句

#include<bits/stdc++.h> using namespace std; int main() {int a, b, s = 1;cin>>a>>b;a %= 7; //使a的值為a % m，本題中m為7for(int i = 0; i < b; ++i)s = (s * a) % 7;switch(s)//從周日過了s天{case 0:cout<<"Sunday";break;case 1:cout<<"Monday";break;case 2:cout<<"Tuesday";break;case 3:cout<<"Wednesday";break;case 4:cout<<"Thursday";break;case 5:cout<<"Friday";break;case 6:cout<<"Saturday";break;}return 0; }

解法2：遞推，用二維字符數組

#include<bits/stdc++.h> using namespace std; int main() {int a, b, v[10005];//v[i]表示a^b%7的值，為0~6，表示周日到周六char s[7][20] = {"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};//s[0]~s[6]分別對應周日到周六的字符串cin>>a>>b;a %= 7;//a為a % mv[1] = a;for(int i = 2; i <= b; ++i)v[i] = (v[i-1] * a) % 7;cout<<s[v[b]];return 0; }

解法3：遞歸，用string類數組

#include<bits/stdc++.h> using namespace std; int solve(int a, int b)//求a^b%7的值，結果為0~6，表示周日到周六 {if(b == 1)return a;elsereturn (solve(a, b - 1) * a) % 7; } int main() {int a, b;string s[7] = {"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};//s[0]~s[6]分別對應周日到周六的字符串cin>>a>>b;cout<<s[solve(a % 7, b)];//solve(a % 7, b)返回0~6，表示周日到周六return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1083：计算星期几 | OpenJudge NOI 小学奥数 7831的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。