【题目来源】
https://www.luogu.com.cn/problem/B2075
【题目描述】
幂 a^b 的末 3 位数是多少?
【输入格式】
两个正整数 a,b。1≤a≤100,1≤b≤10000。
【输出格式】
从高位到低位输出幂的末三位数字,中间无分隔符。若幂本身不足三位,在前面补零。
【输入样例1】
2 3
【输出样例1】
008
【输入样例2】
7 2011
【输出样例2】
743
【算法分析】
● 由于 1≤a≤100,1≤b≤10000,如果硬算 a^b 的话,最大可以达到 100^10000,会产生溢出,显然是不可行的。 解决方法一是利用公式 (a*b)%p=(a%p*b%p)%p 边取模边运算;方法二是直接用快速幂求解。其本质也是利用了方法一中的公式。
● printf() 参数:%0nd 和 %nd 的用法_%0nd:https://blog.csdn.net/hnjzsyjyj/article/details/143719009
%nd → 表示输出的整数宽度至少为 n 位,不足 n 位左填充空格。位数大于 n 则输出实际位数。
%0nd → 表示输出的整数宽度至少为 n 位,不足 n 位左填充 0。位数大于 n 则输出实际位数。
【算法代码:快速幂】
#include <bits/stdc++.h>
using namespace std;const int MOD=1000;int fastPow(int a,int b) {int ans=1;while(b) {if(b & 1) ans=ans*a%MOD;a=a*a%MOD;b>>=1;}return ans%MOD;
}int main() {int a,b,t;scanf("%d%d",&a,&b);t=fastPow(a,b);if(t>=100) printf("%d",t);else if(t<100 && t>=10) printf("0%d",t);else printf("00%d",t);return 0;
}/*
in:7 2011
out:743
*/
【算法代码:(a*b)%p=(a%p*b%p)%p】
#include <bits/stdc++.h>
using namespace std;const int MOD=1000;int main() {int a,b,t=1;scanf("%d%d",&a,&b);while(b--) {t*=a;t%=MOD;}if(t>=100) printf("%d",t);else if(t<100 && t>=10) printf("0%d",t);else printf("00%d",t);return 0;
}/*
in:7 2011
out:743
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/143168167
https://blog.csdn.net/hnjzsyjyj/article/details/143135845
https://blog.csdn.net/hnjzsyjyj/article/details/146273704
https://blog.csdn.net/hnjzsyjyj/article/details/146285970
https://blog.csdn.net/m0_58373406/article/details/136348089