算法|数学与数论|快速幂和光速幂

数学与数论|快速幂和光速幂

1.快速幂（递归）

2.快速幂（二进制）

3.快速幂（取���）

4.光速幂（根号分治）

心有猛虎，细嗅蔷薇。你好朋友，这里是锅巴的C\C++学习笔记，常言道，不积跬步无以至千里，希望有朝一日我们积累的滴水可以击穿顽石。

快速幂，二进制取幂(Binary Exponentiation，也称平方法），是一个在O（logn）的时间内计算an的小技巧，而暴力计算需要O（n）的时间。

在a，n很大的情况下，暴力计算不适用，但这种情况会要求输出对mod取模的答案。所以我们需要一种方法，既能保证答案在0~mod-1之内，又能使时间复杂度在可接受范围内。而快速幂则是基于分治的思想，用于解决这种问题的算法。

快速幂（递归）

实践代码：

#includeusing namespace std;#define int long long#define endl '\n'int qpow(int a,int b){    if(b==0) return 1;    if(b==1) return a;    int c = qpow(a,b/2);//递归的思想    if(b%2==1) return c*c*a;//b是奇数，除以2会向下取整    else return c*c;}

快速幂（二进制）

注意：

实践代码：

int qpow(int a,int b){    int res = 1;    while(b){        if(b&1) res*=a;//检查二进制当前位是否有1        a*=a;//递推计算        b>>=1;    }    return res;}

快速幂（取模）

注意:

因为一般题目让我们所求的幂元很大，但其实就是在二进制的基础上增加了取模运算。

实践代码：

const int mod = 1e9 +7;//(题目给定不同模时，替换就行)int qpow(int a,int b){    int res = 1;    while(b){        if(b&1) res*=a,res%=mod;//检查二进制当前位是否有1        a*=a;a%=mod;        b>>=1;    }    return res%mod;}

题目：

给你三个整数a,b,p,求 ab mod p。

输入描述:

输入只有一行三个整数，分别代表a,b,p。

输出描述:

输出一行一个字符串a^b mod p=s,其中a,b,p分别为题目给定的值，s为运算结果。

示例1

输入

2 10 9

输出

2^10 mod 9=7

备注

样例解释

2^10 = 1024,1024 mod 9 = 7。

数据规模与约定

对于100%的数据，保证0≤a,b≤231，a+b>0,2≤p≤231。

实践代码：

#includeusing namespace std;#define int long long#define endl '\n'int qpow(int a,int b,int p){    int res = 1;    while(b){        if(b&1) res*=a,res%=p;//检查二进制当前位是否有1        a*=a,a%=p;        b>>=1;    }    return res%p;}void solve(){    int a,b,mod;cin>>a>>b>>mod;    cout    ios::sync_with_stdio(false);    cin.tie(0);cout.tie(0);    int t=1;    //cint;    while(t--){        solve();    }    return 0;}//底数x    l[0] = h[0] = 1;    for(int i=1;i   int x,n;cinxn;//底数x和查询次数n   lpow(x);   while(n--){       int c;cinc;//查询x的幂c       cout//底数x    l[0] = h[0] = 1;    for(int i=1;i   int x,n;cinxn;//底数x和查询次数n   lpow(x);   while(n--){       int c;cinc;//查询x的幂c       cout