解法一:
最朴素的方法,直接循环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分
4 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复