[编程笔记]-Binary_Exponentiation快速幂

思想

把a的k次方分解成a的（2的次方）次方之积。

也就是把k分成2的不同次方相加嘛。容易得到，2的每个次方最多只会出现一次（不然就能进位算进更高一次的次方里面去了）。

差不多就是这样。

时间复杂度

O(logk)（k为幂数）

实现

递归法

很简单，根据思想就能得出。
每次都把次方平均分，如果是奇数，就在结果处额外乘一个n即可，然后递归次方的二分之一，直到0次方。

迭代法

事实上，可以把次数写出二进制写法，然后就可以根据每一位上是否为1分出不同的加项了。

每次幂次左移一位，不要忘了把底数平方一次（实现一次平方），然后根据当前幂次的二进制最低位来判断是否要乘入结果。

可能讲的不是很清楚，但差不多应该也讲清了思路，带着代码可能更好理解。

代码

递归法

int qm(int a,int b,int p){
    if(b==0)return 1;
    int t=qm(a,b/2,p);
    if(b%2==0){
        return (ll)t*t%p;
    }
    else{
        return (ll)t*t*a%p;
    }
}

注：实测这份代码的精度没有下面那份高，速度也不够好，所以还是推荐迭代法。

迭代法

int qm(int a,int b,int p){
    int res=1;
    while(b){
        if(b&1)res=(ll)res*a%p;
        a=(ll)a*a%p;
        b>>=1;
    }
    return res;
}

应用——乘法逆元

以后应该会专门写一篇介绍乘法逆元，到时候就把这部分复制过去这里就顺便介绍一下，专门讲用快速幂解决的方法。

定义

若b与m互质，满足b|a，a/b≡ax(mod m)，则称x为b模m的逆元，记作b^-1（是标记，不是b的-1次方，可以是整数）

然后就可以把÷b的情况转化为×b的逆元的情况，在编程中，这就准确多了。

性质

a/b≡ab^-1 (mod m)

b*a/b≡b*ab^-1 (mod m)

a≡a*b*b^-1 (mod m)

-> b*b^-1≡1 (mod m)

（最后一步的条件是a%m!=0，虽然a与m不一定互质，但由于a有b这个和m互质的质因子，所以a%m!=0）

即为:
bx≡1 (mod m)

公式美化：ax≡1 (mod m)

计算逆元

在快速幂求解过程中中，一般要求m为质数。

因此，ax≡1 (mod p)

根据费马小定理，a^p-1≡1 (mod p)

然后把根据费马小定理的这个式子拆出来一个
a：a*a^a-2≡1 (mod p)

所以a^p-2=x，就是a模p的逆元。

又因p是质数，所以p>=2，因此p-2>=0。

因此，求a模p的逆元，也就是求a^p-2

但是，若p与a不互质，则无解，因为不可能出现余数。同时，这也是费马小定理使用前提和乘法逆元定义中的一部分。

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int n,a,p;

int qmi(int a,int b,int q){
    int res=1;
    while(b){
        if(b&1)res=(ll)res*a%p;
        a=(ll)a*a%p;
        b>>=1;
    }
    return res;
}

int main(){
    cin.tie(0);
    cin>>n;
    while(n--){
        cin>>a>>p;
        if(a%p!=0)cout<<qmi(a,p-2,p)<<endl;//由于p是质数，所以二者不互质就只有倍数关系
        else cout<<"impossible"<<endl;
    }
    return 0;
}

完结撒花o(￣︶￣)o