解法一:
最朴素的方法,直接循环b次,求出ab的结果,最后对c取模
#include using namespace std; int main() { int a,b,c,ans = 1; cin >> a >> b >> c; for(int i = 1;i <= b;i++) { ans *= a; } cout << (ans % c) << endl; return 0; }
但是这么写有问题,如果b的值太大,会导致溢出和超时(指数爆炸),这里的复杂度是O(n)
解法二:快速幂
ab mod m 这个式子中,最容易导致超时的部分是ab,我们可以先思考一下这部分怎么算才快
假设,在草稿计算310,我们可以分解成310 = (32)5 = 95 = 9 * 94 = 9 * (81)2 = 9 * (811)2
可以发现一些规律:当指数为偶数的时候,将指数除以2,底数平方;当指数为奇数的时候,提取出一次方的底数,再将指数除以2,底数平方
这时候就可以设三个变量,设base为底数,设index为指数,设mod取模数,有了变量和规律,代码就不难了
另外,这里也要考虑数据范围问题,根据题目给出的范围,可能会造成指数爆炸,所以使用C++中long long来存储数据
这个的复杂度是O(log2n)
typedef long long ll; #include using namespace std; ll fast_pwoer(ll base,ll index,ll mod) { ll ans = 1; base %= mod; //指数为循环次数 while (index) { //判断奇偶性 if (index % 2 == 1) { ans = (ans * base) % mod; } base = (base * base) % mod; index /= 2; } return ans; } int main() { int a,b,c; cin >> a >> b >> c; cout << (fast_pwoer(a,b,c)) << endl; return 0; }
0.0分
12 人评分
C语言程序设计教程(第三版)课后习题9.4 (Java代码)浏览:1416 |
淘淘的名单 (C语言代码)答案错误???浏览:593 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:505 |
WU-输入输出格式练习 (C++代码)浏览:1076 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:672 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:662 |
【计算直线的交点数】 (C语言代码)浏览:916 |
母牛的故事 (C语言代码)浏览:478 |
【计算球体积】 (C语言代码)浏览:1548 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:728 |