快速幂与快速乘

a^b

题目描述

求 a 的 b 次方对 p 取模的值，其中 0≤a,b≤10^9 , 0<p≤10^9

输入
三个用空格隔开的整数a,b和p。

输出
一个整数，表示a^b mod p的值。

样例输入
2 3 9

样例输出
8

思路

普通求幂时间复杂度为O(b),会TLE
设b的二进制表示有k位，c_i为0或1，则

而

所以计算k-1次就可以求出答案，时间复杂度优化到O(logb)

还可以用递归的思想

代码

非递归写法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quick_power(ll a, ll b, ll p){ // 快速幂
    ll ans = 1 % p;
    while(b){
        if(b & 1) ans = a*ans % p;
        a = a*a % p;
        b >>= 1;
    }
    return ans;
}
int main(){
    
    ll a,b,p;
    cin>>a>>b>>p;
    ll ans = quick_power(a,b,p);
    cout<<ans;
}

递归写法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quick_power(ll a, ll b, ll p){ //快速幂
    if(b == 0) return 1 % p;
    ll res = quick_power(a,b>>1,p)%p;
    if(b&1) return (res * res % p) * a % p; 
    else return  res * res % p;

}
int main(){
    ll a,b,p;
    cin>>a>>b>>p;
    ll ans = quick_power(a, b, p);
    cout<<ans;
}

64位整数乘法

题目描述

求a乘b对p取模的值，其中1≤a,b,p≤1018

输入
输入3个long long型整数，a,b,p

输出
输出a*b%p的值

样例输入
250182048980811753
413715569939057660
133223633696258584

样例输出
19308689043391716

思路

与快速幂类似

而

同样也可以用递归的思想

代码

非递归写法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quick_mul(ll a, ll b, ll p){ // 快速乘
    ll ans = 0;
    while(b){
        if(b&1) ans = (ans + a) % p;
        a = a*2%p;
        b >>= 1;
    }
    return ans;
}
int main(){
    ll a,b,p;
    cin>>a>>b>>p;
    ll ans = quick_mul(a,b,p);
    cout<<ans;
}

递归写法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quick_mul(ll a, ll b, ll p){ // 快速乘
    if(b == 0) return 0;
    ll res = quick_mul(a,b>>1,p) %p;
    if(b & 1) return ((res+res)%p+a) %p;
    else return (res+res)%p; 
}
int main(){
    ll a,b,p;
    cin>>a>>b>>p;
    ll ans = quick_mul(a,b,p);
    cout<<ans;
}

快速幂与快速乘

原文：https://www.cnblogs.com/jccodingforfun01/p/14220497.html