四川盐亭网站制作公司

01二分快速幂-创新互联

1、模幂运算

创新互联建站服务项目包括东阳网站建设、东阳网站制作、东阳网页制作以及东阳网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，东阳网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到东阳省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

  • 这里求  的  次幂(次方)对  取余数的计算，被称为模幂运算，本文会针对以上的式子，根据数据范围提供完全不同的算法来进行讲解，确保正确性的前提下，以求达到时间和空间的平衡；

  • 高端的算法往往只需要采用最朴素的诠释方式。

朴素算法

1）枚举

  • 直接一个  次的循环，枚举对  的  次乘法：

  • 最后进行取模运算（c++中的 '%' 符号等价于数学中的取模 mod）；

  • c++代码实现如下：

int f(int a, int b, int c) {
    int ans = 1;
    while(b--)
        ans = ans * a;
    return ans % c;
}

这段代码有没有问题呢？

溢出问题：首先，在数据量比较大的时候，运算结果会出现负数，这是因为int 的取值范围是 [-2^31,2^31]，超过后就会溢出，结果就和预期的不符了；

时间复杂度：其次，这个算法的时间复杂度是O(b)的，当b很大的时候，明显是无法满足时间要求的，尤其是写服务器代码的时候，时间复杂度尤为重要，10个、100个、1000 个玩家出现这样的计算时，时间消耗都是成倍增长的，非常占用服务器 CPU 资源；

那么，我们先保证正确性，确保计算过程中不会溢出，这里就需要用到数论里面一些简单的知识：模乘。

2） 模乘

模乘满足如下公式：

证明如下：

所以我们可以对朴素算法进行一些改进，改进如下：

int f(int a, int b, int c) {
    int ans = 1 % c;
    while(b--)
        ans = ans * a % c;
    return ans;
}

利用模乘运算，可以先模再乘，每次运算完毕确保数字是小于模数的，这样确保数字不会太大而造成溢出，但是这里没有考虑一种情况，就是  有可能是负数；

3） 负数考虑

需要再进行一次改进，改进版如下：

int f(int a, int b, int c) {
    a = (a % c + c) % c;
    int ans = 1 % c;
    while(b--)
        ans = ans * a % c;
    return ans;
}

我们发现只需要多加一句话：

a%c 是为了确保模完以后a的绝对值小于c，如图上图所示； 

再加上c是为了保证结果是正数，如上图所示；

最后又模上c是为了确保a是正数的情况也能准确让结果落在(0,c)的范围内，如上图所示；

这样改完还有哪些问题呢？？？

1、溢出问题：溢出问题仍然存在，只要c的范围是 [-2^31,2^31],ans和a的范围就在(0,c) ，ans*a的范围就是(0,c^2) ，最坏情况就是(0,2^62) ，还是超过了int的范围；

2、时间复杂度：时间复杂度仍然是O（b）的，而且每次都有一个取模运算，常数时间变大了；

为了改善溢出问题，我们可以在相乘的时候转成long long来避免，c++ 代码实现如下：

int f(int a, int b, int c) {
    a = (a % c + c) % c;
    int ans = 1 % c;
    while(b--)
        ans = (long long)ans * a % c;
    return ans;
}

溢出问题暂且告一段落，接下来让我们考虑下如何改善时间复杂度的问题（也许有人会问，如果c模数的范围是long long,   又该怎么办呢？）；

2、循环节

1） 小数据分析

2）算法实现

算法时间复杂度为O(K) ；

基于K的不确定性，并且时间复杂度应该是算最坏情况下的，所以这个算法的实际时间复杂度是O(c)；

c++代码实现如下：

#define MAXN 100005
int F[MAXN+1], FPos[MAXN+1];
int f(int a, int b, int c) {
    memset(FPos, -1, sizeof(FPos));
    F[0] = 1 % c;
    FPos[ F[0] ] = 0;
    for(int i = 1; i<= b; ++i) {
        F[i] = F[i-1] * a % c;
        int &pre =  FPos[ F[i] ];
        if( pre == -1) {
            pre = i;
        }else {
            int K = i - pre;
            int Index = ( b - pre ) % K + pre;
            return F[Index];
        }
    }
    return F[b];
}
2、二分快速幂

1) 递归实现
#define ll long long
ll f(ll a, ll b, ll c) {
    if (b == 0)
        return 1 % c;
    ll v = f(a*a % c, (b>>1), c);
    if (b & 1)
        v = v * a % c;
    return v;
}

  • 代码实现非常简单，根据 c++ 整数除法是取下整的特性，偶数和奇数的除法可以统一处理，然后用位运算进行一部分优化；

  • 1）右移一位相当于 除2；

  • 2）位与(&) 1 用于判断奇偶性；

2) 二进制优化实现

c++ 代码实现如下

#define ll long long
ll f(ll a, ll b, ll c){
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % c;     // 1）
        a = a * a % c;                   // 2）
        b >>= 1;                         // 3）
    }
    return ans;
}

  • 1）和 3）是配合着做的，检查n的第i位二进制低位否是1，如果是则乘上对应的a次幂：a^(ni)其中ni=2^i;

  • 2）依次求出a1 a2 a4 a8........；

  • 这个算法的时间复杂度为O(logb)，相比递归算法减少了一些常数消耗；

3、模数为 64 位整数

c++ 代码实现如下

#define ll long long
ll Product_Mod(ll a, ll b, ll c) {
    ll sum = 0;
    while(b) {
        if(b & 1) sum = (sum + a) % c;
        a = (a + a) % c;
        b >>= 1;
    }
    return sum;
}
ll f(ll a, ll b, ll c) {
    ll ans = 1;
    while(b) {
        if(b & 1) sum = Product_Mod(sum, a, c);
        a = Product_Mod(a, a, c);
        b >>= 1;
    }
    return ans;
}
4、时间复杂度总结

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


当前文章：01二分快速幂-创新互联
文章URL：http://scyanting.com/article/ceegco.html

其他资讯