【题目链接】
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. 幂取模
a b % m = ( a b − 1 ⋅ a ) % m = ( a b − 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
这就是求 a b % m a^b \%m ab%m的递推公式
其中b = 1时 a b % m = a % m a^b\%m = a \%m ab%m=a%m
【解题思路】
本题要求的是幂的末两位数，即为幂的值模100。根据幂取模的递推公式，若要求 a b % m a^b\%m ab%m，可以有以下三种解法。
1. 递推
设v[i]表示 a b % m a^b \% m ab%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 \% m ab%m的值
要求该值，需要先求 a b − 1 % m a^{b-1}\% m ab−1%m的值，代入公式 a b % m = ( a b − 1 % m ⋅ a % m ) % m a^b\%m = (a^{b-1}\%m \cdot a \%m)\%m ab%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;
}
