【蓝桥杯】ADV-204 快速幂

• 2019 年 11 月 13 日
• 筆記

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_42449444/article/details/102989593

题目描述：

给定A, B, P，求(A^B) mod P。

输入描述：

输⼊共⼀⾏。 第⼀⾏有三个数，N, M, P。（A, B为long long范围内的⾮负整数，P为int内的⾮负整数）。

输出描述：

一个整数，表示箱子剩余空间。

输入样例：

2 5 3

输出样例：

2

解题思路：

整数快速幂的时间复杂度是

，可以防止TLE，有非递归和递归俩种算法，我是看晴神的《算法笔记》上理解的。

AC代码：

#include <bits/stdc++.h>  using namespace std;  typedef long long ll;    ll quickPow(ll x,ll n,ll m)    //整数快速幂,计算x^n%m  {      ll ans = 1;      x %= m;      while(n)      {          if(n&1)   //奇数          {              ans = ans*x%m;          }          x = x*x%m;          n >>= 1;      }      return ans;  }    ll binaryPow(ll x,ll n,ll m)    //整数快速幂,计算x^n%m递归求解  {      if(n == 0) return 1;    //若n为0,则x^0=1      else if(n&2)    //若n为奇数,转换为n-1      {          return n*binaryPow(x,n-1,m)%m;      }      else    //若n为偶数,转换为n/2      {          ll ans = binaryPow(x,n/2,m);          return ans*ans%m;      }  }    int main()  {      ios::sync_with_stdio(false);      cin.tie(0),cout.tie(0);      ll a,b,m;      cin >> a >> b >> m;      cout << quickPow(a,b,m) << endl;      return 0;  }