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

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

1.快速幂（递归）

2.快速幂（二进制）

3.快速幂（取���）

4.光速幂（根号分治）

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

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

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

快速幂（递归）

实践代码：

#include
using 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 =

数据规模与约定

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

实践代码：

#include
using 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