信息学奥赛一本通 2024：【例4.10】末两位数
【题目链接】
ybt 2024：【例4.10】末两位数
【题目考点】
1. 同余定理
根据同余定理，有：
(a∗b)%m=(a%m∗b%m)%m(a*b)\%m = (a\%m * b\%m)\%m(a∗b)%m=(a%m∗b%m)%m
2. 幂取模
ab%m=(ab−1⋅a)%m=(ab−1%m⋅a%m)%m\begin{aligned} a^b\%m &= (a^{b-1} \cdot a) \% m \\ &= (a^{b-1}\%m \cdot a \%m)\%m \end{aligned}ab%m=(ab−1⋅a)%m=(ab−1%m⋅a%m)%m
这就是求ab%ma^b \%mab%m的递推公式
其中b = 1时ab%m=a%ma^b\%m = a \%mab%m=a%m
【解题思路】
本题要求的是幂的末两位数，即为幂的值模100。根据幂取模的递推公式，若要求ab%ma^b\%mab%m，可以有以下三种解法。
1. 递推
设v[i]表示ab%ma^b \% mab%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);求ab%ma^b \% mab%m的值
要求该值，需要先求ab−1%ma^{b-1}\% mab−1%m的值，代入公式ab%m=(ab−1%m⋅a%m)%ma^b\%m = (a^{b-1}\%m \cdot a \%m)\%mab%m=(ab−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; }总结
以上是生活随笔为你收集整理的信息学奥赛一本通 2024：【例4.10】末两位数的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 信息学奥赛一本通 1108：向量点积计算
- 下一篇： 二维数组的遍历方法