python

3.8 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

快速幂与快速乘

一、快速幂

现有两个整数m、n，求m^n 除以1000000007之后的余数。

输入：输入整数m、n，用1个空格隔开，占1行。

输出：输出m^n除以1000000007之后的余数，占1行。

限制：1<=m<=100，1<=n<=10^9

输入示例： 5 8

输出实例： 390625

解决算法复杂度问题

如果用最直接的方法求x^n，我们需要进行n-1次乘法运算，算法复杂度为O(n)。

快速幂的思想其实是二进制的思想：

(21)_{10}=(10101)_2

从右到左遍历每一个二进制数位,分两条线进行：

数字a每次平方后写入a,即a*=a
每个数位检查当前二进制数位是否为1,如果为1,则需要多累乘一个当前的a

int qmi(int a, int b){
    int ans = 1;
    while(b){
        if(b&1) ans*= a; //当b为奇数时，乘以余下的一个a
        b >>= 1;//位运算，右移1位，相当于除以2
        a*= a;
    }
    return ans;
}

这样，递归函数的参数n逐次减半，因此算法复杂度为O(logn)。

这样，递归函数的参数n逐次减半，因此算法复杂度为O(logn)。

####　解决取模运算问题在遇到 求某计算结果除以M（本题中是1000000007）之后的余数 这类题时，可以按下述方法计算（这里a除以b之后的余数记作a\%b）。

计算加法时，每相加一次执行一次\%M
计算减法时，给被减数加上M之后，先算减法，后算\%M
计算乘法时，每相乘一次执行一次\%M

引理`1`：积的取余等于取余的积的取余

(a*b)\%M=[(a\%M)*(b\%M)]\%M

证明：设a除以M的余数和商分别为ar、aq， b除以M的余数和商分别为br、bq，即 a/M=aq……ar， b/M=bq……br，

则有：

$a∗b =(aq∗M+ar)∗(bq∗M+br) =aq∗bq∗M^2 +ar∗bq∗M+aq∗br∗M+ar∗br =(aq∗bq∗M+ar∗bq+aq∗br)∗M+ar∗br$

即易得： (a*b)\%M=(ar*br) \%M=[(a\%M)*(b\%M)]\%M

引理2:幂的取余等于取余的幂再取余

公式：a^b\%M=(a\%M)^b\%M

证明： (a\%M)^b\%M\\= [(a*1)\%M]^b\%M\\=\{[(a\%M)*(1\%M)]\%M\}^b\%M\\=[(a\%M)\%M]^b\%M

由上面公式迭代： [(a\%M)^b]\%M=a^b\%M 因此，解决了上述两个问题，我们就可以实现 快速幂 的算法代码了：

#include <iostream>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
/*
测试用例：
5 8

结果：
390625
*/
//快速幂
LL ksm(LL a, LL b) {
    LL ans = 1;
    a %= mod;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        b >>= 1; //位运算，右移1位，相当于除以2
        a = (a * a) % mod;
    }
    return ans;
}
int main() {
    LL a, b;
    cin >> a >> b;
    printf("%lld\n", ksm(a, b));
    return 0;
}

二、快速乘

同理，易得 快速乘 的算法：快速乘主要用于防止有两个较大的数相乘而直接乘爆, 因为是加法, 怎么都不可能加爆，所以目的就是为了防止爆范围。

#include <iostream>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
/*
测试用例:
10000000 10000000

答案：
999300007
*/
//快速乘，计算a*b%mod
LL ksc(LL a, LL b) {
    LL ans = 0;
    a %= mod;
    while (b) {
        if (b & 1) ans = (ans + a) % mod;
        b >>= 1; //位运算，右移1位，相当于除以2
        a = (a + a) % mod;
    }
    return ans;
}
int main() {
    LL a, b;
    cin >> a >> b;
    printf("%lld\n", ksc(a, b));
    return 0;
}

三、总结

快速幂 解决a^b\%mod
快速乘 解决a*b\%mod

3.8 KiB Raw Permalink Blame History Unescape Escape