本文共 702 字,大约阅读时间需要 2 分钟。
计算一个数的幂次,其实是不用计算N次的
//递归快速幂int qpow(int a, int n){ if (n == 0) return 1; else if (n % 2 == 1) return qpow(a, n - 1) * a; else { int temp = qpow(a, n / 2); return temp * temp; }}
快速幂取模
//递归快速幂(对大素数取模)#define MOD 1000000007typedef long long ll;ll qpow(ll a, ll n){ if (n == 0) return 1; else if (n % 2 == 1) return qpow(a, n - 1) * a % MOD; else { ll temp = qpow(a, n / 2) % MOD; return temp * temp % MOD; }}
//非递归快速幂int qpow(int a, int n){ int ans = 1; while(n){ if(n&1) //如果n的当前末位为1 ans *= a; //ans乘上当前的a a *= a; //a自乘 n >>= 1; //n往右移一位 } return ans;}
转载地址:http://xsmv.baihongyu.com/