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，则

\[b = \sum\limits_{i=0}^{k-1} c_i*2^i \]

\[a^b = a^{\sum\limits_{i=0}^{k-1} c_i*2^i} = \prod_{k=0}^{k-1}a^{c_{i}*2^i} = \prod_{k=0}^{k-1}{(a^{2^i})}^{c_i} \]

而

\[a^{2^i} = a^{2^{i-1}}*a^{2^{i-1}} \]

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

还可以用递归的思想

\[a^b = \left\{ \begin{aligned} & a^{\frac b2}*a^{\frac b2} &(b为偶数) \\ & a^{\frac {b-1}2}*a^{\frac {b-1}2}*a& (b为奇数)\\ \end{aligned} \right. \]

代码

非递归写法

#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

思路

与快速幂类似

\[b = \sum\limits_{i=0}^{k-1} c_i*2^i a*b = a*\sum\limits_{i=0}^{k-1} c_i*2^i = \sum\limits_{i=0}^{k-1} c_i*(a*2^i) \]

而

\[a*2^i = a*2^{i-1}*2 \]

同样也可以用递归的思想

\[a*b = \left\{ \begin{aligned} & a*{\frac b2} + a*{\frac b2}&(b为偶数) \\ & a*{\frac {b-1}2} + a*{\frac {b-1}2}+a& (b为奇数)\\ \end{aligned} \right. \]

代码

非递归写法

#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;
}