算法工程师数学题（5）次方求模---快速幂取模算法

2019-04-13 13:31发布

站内文章 / 模拟电子
16782 0 1042
问题：求a的b次方取c的模的值公式: (a*b)%c=(a%c)*(b%c)%c
递归法：#include #include using namespace std; int fun(int a, int b, int c) { int ans=1; if (b == 0) return 1 % c; if (b == 1) return a % c; ans = fun(a, b / 2, c); ans = ans * ans % c; if (b%2 == 1) ans = ans * a % c;//此句的作用是？？ return ans; } int main(void) { int a, b, c,n; cout << "输入多少次:" << endl; cin >> n ; while (n--) { cout << "输入a的b次幂对c求余数的abc:" << endl; cin >> a >> b >> c; cout << "a的b次幂对c求余数是：" <循环法：int fun(int a, int b,int c) { if (b == 1) return a%c; int term = pow(a, b / 2); term = term*term%c; if (b % 2) //当b是奇数，乘以一个a term = a*term%c; return term; }

热门文章