上海计算机学会2024年7月月赛C++乙组T1幂的运算
发布时间
阅读量：
阅读量
幂的运算
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定三个正整数 a,b 及 c，请计算
a^b mod c
输入格式
- 第一行，三 个整数表示 a,b,c
输出格式
单个整数：表示答案。
数据范围
- 30% 的数据，1≤a,b,c≤10
- 60% 的数据，1≤a,b,c≤5000
- 100% 的数据，1≤a,c≤109，1≤b≤1018
样例数据
输入:
2 16 1000
输出:
536
解析：快速幂，可以使用二进制分解的快速幂，详见代码：
#include<bits/stdc++.h>
using namespace std;
long long a, b, c;
int main() {
cin >> a >> b >> c;
long long m = a;//对应b二进制每一位的权值
long long ans = 1;
while (b > 0) {//二进制分解
if (b % 2 == 1) {//该位为1，则乘该位的权值
ans *= m;
ans %= c;
}
m *= m;//权值平方，即为下一位的权值
m %= c;
b /= 2;//去掉最后一位
}
cout << ans;
return 0;
}
还可以采用递归的办法求快速幂，详见代码：
#include<bits/stdc++.h>
using namespace std;
long long a, b, c;
long long f(long long x) {
if (x == 0) return 1;
long long ret = f(x / 2);
if (x % 2 == 0) {
return ret * ret % c;
} else {
return ret * ret % c * a % c;
}
}
int main() {
cin >> a >> b >> c;
cout << f(b);
return 0;
}
全部评论 (0)
还没有任何评论哟~