2708: 【例29.2】 幂的末尾
内存限制:64 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:97
解决:67
题目描述
幂$a^b$的末$3$位数是多少?
输入
两个正整数$a$,$b$。($1≤a≤100$,$1≤b≤10000$)
输出
从高位到低位输出幂的末三位数字,中间无分隔符。若幂本身不足三位,在前面补零。
样例输入 复制
7 2011
样例输出 复制
743
提示
1.3 模运算的核心规律:先取模再相乘
先放下快速幂,说说为什么“过程中取模”是安全的。模运算有一个非常重要的性质,对任意整数x、y、m,都有:
(x * y) mod m = ((x mod m) * (y mod m)) mod m
话句话说, 乘法运算中,先取模再乘,和乘完再取模,结果完全一样。 这个性质对单次乘法成立,对连乘自然也就成立。a^b本质上是b个a连乘,所以每一步都对1000取模,最终得到的余数和完整算完再取模完全一致。
生活里也有类似的经验:看日期的时候,今天是星期几只取决于今天,跟你是从公元元年算了多少天过来没有关系;算时间超过24小时会自动进位,但“现在是几点”只需要看最后一位循环。
#include<bits/stdc++.h>
using namespace std;
int a,b,ans=1;
int main(){
cin>>a>>b;
for(int i=1;i<=b;i++){
ans *= a;
ans %=1000;
}
printf("%03d",ans);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
int ans = 1;
int base = a % 1000;
while (b > 0) {
if (b & 1) { // 判断b最低位是否为1
ans = ans * base % 1000;
}
base = base * base % 1000;
b >>= 1; // b右移一位
}
printf("%03d\n", ans);
return 0;
}