解法一:
最朴素的方法,直接循环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语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:576 |
模拟计算器 (C语言代码)浏览:947 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:601 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:683 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:620 |
C语言训练-求PI* (C语言代码)浏览:628 |
三角形 (C++代码)记忆化搜索浏览:1300 |
简单的a+b (C语言代码)浏览:651 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:484 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1477 |