【題目鏈接】

ybt 2024：【例4.10】末兩位數(shù)

【題目考點(diǎn)】

1. 同余定理

根據(jù)同余定理，有：
$(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時(shí)$a^b\%m=a\%m$

【解題思路】

本題要求的是冪的末兩位數(shù)，即為冪的值模100。根據(jù)冪取模的遞推公式，若要求$a^b\%m$，可以有以下三種解法。

1. 遞推

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

2. 迭代

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

3. 遞歸

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

【題解代碼】

解法1：迭代

#include<bits/stdc++.h> using namespace std; int main() {int n, res = 1;cin >> n;for(int i = 1; i <= n; ++i)res = (res * 1992) % 100;cout << res;return 0; }

解法2：遞推

#include<bits/stdc++.h> using namespace std; int main() {int n, v[2005];//v[i]表示1992^i的末兩位cin >> n;v[1] = 1992 % 100;for(int i = 2; i <= n; ++i)v[i] = v[i-1] * 1992 % 100;cout << v[n];return 0; }

解法3：遞歸

#include<bits/stdc++.h> using namespace std; int solve(int i)//求1992^i的末兩位 {if(i == 1)return 92;elsereturn solve(i-1) * 1992 % 100; } int main() {int n;cin >> n;cout << solve(n);return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 2024：【例4.10】末两位数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。