二分快速幂
求a的b次方,自定义pow库函数:
pow(a, b)是数学头文件math.h里面有的函数,但是它返回值是double类型,数据有精度误差。
可以改成这样:
long long pow(long long a, long long b){
long long ret = 1;
for(long long i = 1; i <= b; i ++){
ret *= a;
}
return ret;
}
二分快速幂:
数据量大会超时,使用自定义的pow也要超时,这时候要使用二分快速幂了
代码模板:
递归写法
const int MOD=1e9+7;
typedef long long ll;
ll pow_mod(ll a, ll b){//a的b次方
if(b == 0) return 1%MOD;
ll ret = pow_mod(a, b/2);
ret = ret * ret % MOD;
if(b % 2 == 1) ret = ret * a % MOD;
return ret;
}
循环写法:
#include<bits/stdc++.h>
using namespace std;
int pow_mod(int a, int n, int mod)
{
long long ans = 1;
while(n){
if(n&1){
ans = (ans * a) % mod;
}
a = (a * a) % mod;
n >>= 1;
}
return ans;
}
int main()
{
int a, n, mod;
cin >> a >> n >> mod;
cout << pow_mod(a, n, mod);
}
快速乘:
LL mul(LL a, LL b, LL p){//快速乘,计算a*b%p
LL ret = 0;
while(b){
if(b & 1) ret = (ret + a) % p;
a = (a + a) % p;
b >>= 1;
}
return ret;
}
原文链接: https://www.cnblogs.com/fisherss/p/10012340.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/285691
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!