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;
}