【题目来源】
洛谷：P1226 【模板】快速幂 - 洛谷
【题目描述】
给你三个整数 \(a,b,p\)，求 \(a^b \bmod p\)。
【输入】
输入只有一行三个整数，分别代表 \(a,b,p\)。
【输出】
输出一行一个字符串 a^b mod p=s，其中 \(a,b,p\) 分别为题目给定的值， \(s\) 为运算结果。
【输入样例】
2 10 9
【输出样例】
2^10 mod 9=7
【算法标签】
《洛谷 P1226 【模板】快速幂》 #数学# #递推# #递归#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 使用长整型防止计算溢出int a, b, p; // 底数、指数、模数
int ans; // 存储计算结果/*** 快速幂算法（带模运算）* @param x 底数* @param y 指数* @param z 模数* @return 计算结果 (x^y) mod z*/
int quick(int x, int y, int z)
{int res = 1; // 初始化结果为1while (y) // 当指数不为0时循环{if (y % 2) // 如果当前指数为奇数{res = (res * x) % z; // 乘上当前底数并取模}x = (x * x) % z; // 底数平方并取模y /= 2; // 指数减半}return res;
}signed main()
{// 输入底数、指数和模数cin >> a >> b >> p;// 计算a的b次方模p的结果ans = quick(a, b, p);// 按照格式输出结果printf("%d^%d mod %d=%d", a, b, p, ans);return 0;
}
【运行结果】
2 10 9
2^10 mod 9=7