【模板】快速幂Ⅰ ‖ 模小整数

[编程题]【模板】快速幂Ⅰ ‖ 模小整数

热度指数：2039 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 1024M，其他语言2048M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的三个整数 $a,b,p$ ，计算 $a^b \bmod p$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

一行上输入三个整数 ，表示底数、指数、模数。

输出描述:

对于每一组测试数据，新起一行输出一个整数，代表式子的答案。

示例1

输入

输出

备注:

本题已于下方时间节点更新，请注意题解时效性：
1. 2025-11-28 优化题面文本与格式；缩小  的范围（从  缩小到 ）。模板题为便于测试，将时间限制扩充至 5s，空间限制扩充至 1024MB。

算法知识视频讲解

C++

icepointboy

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        long long a,b,p,res=1;
        cin>>a>>b>>p;
        if(p==1){
            cout<<"0\n";
            continue;
        }
        a%=p;
        while(b){
            if(b&1)
            res=(res*a)%p;
            a=(a*a)%p;
            b>>=1;
        }
        cout<<res<<'\n';
    }
}

发表于 2026-01-23 16:12:04 回复(0)