快速幂

快速幂算法

发布日期: 2021-01-31

阅读次数:

一、a^b

题目

求a的b次方对p取模的值，其中 1<=a,b,p<=10^9
输入描述:
第一行a，第二行b，第三行p。
输出描述:
一个整数，表示a^bmodp的值。

思路

a^16 = (a^8)^2 = ((a^4)^2)^2 = (((a^2)^2)^2)^2
循环16次 vs 循环3次

eg：
a^26 = a^16 * a^8 *a^2=(((a^2)^2)^2)^2 + ((a^2)^2)^2 + (a^2)
26 =16+8+2
26的二进制为11010

11010&1 = 0  a    ans=1     11010>>1 --> 1101   
1101&1 = 1   a^2  ans*=a^2  1101>>1 --> 110   
110&1 = 0    a^4            110>>1 --> 11
11&1 = 1     a^8  ans*=a^8  11>>1 --> 1  
1&1 = 1      a^16 ans*=a^16 1>>1 -->0
意思就是通过位运算减少循环次数，从而避免程序超时

接下来是a^b mod b做法

#include<iostream>
#include<cstdio>    //这里用了scanf和printf也是为了节约时间
using namespace std;
#define ll long long
int main(){
    ll a,b,p;
    scanf("%lld %lld %lld",&a,&b,&p);
    int ans=1;
    while(b){
        if(b&1) ans = ans*a%p;  //当b的最后一位为1 ，则将此时的a乘上
        b>>=1;                  //每次b向右移动一位，表示整除2
        a=a*a%p;                //每次让a翻倍
    }
    printf("%lld",ans%p);
    return 0;
}

二、64位整数乘法

题目（和上一题很类似）

求a*b对p取模的值，其中 1<=a,b,p<=10^18
输入描述:
第一行a，第二行b，第三行p。
输出描述:
一个整数，表示a * b modp的值。

思路

这道题是要先算出a*b再对其结果进行求模（取余），因为a和b的最大值为1e+18，我们知道乘法有的时候会溢出，即使是 longlong 也可能在乘法时爆掉。所以我们寻找一种能高效完成乘法操作并且不会爆 longlong 的算法，也就是快速乘。

代码原理

可以把 a * b这样算：
a * b = a + a + a + …+ a
而
a * 1 = a
a * 2 = 2a
a * 4 = 4a
a * 8 = 8a
…
所以可以推出：
a * (2 ^ k) = 2 ^ k * a

完整代码

#include <iostream>

using namespace std;

typedef long long ll;

int main()
{
    ll a, b, p;
    ll ans = 0;//初始化最终的答案
    cin >> a >> b >> p;

    while (b)  //因为当b为0时将结束循环
    {
        if (b & 1)//若b二进制的第一位为1时执行，否则不执行，一旦遇到0，就将之前累积的a加上
            ans = (ans + a) % p;   
    //eg: b=5 二进制写法为101  第一次循环ans=a a=2a  第二次ans=a a=4a 第三次ans=a+4a a=8a 此时b=0 循环结束

        a = (a * 2) % p;
        b >>= 1;//将b的二进制去掉第一位，同b = b >> 1这样写是为了方便
    }
    cout << ans << endl;

    return 0; 
}