189 8069 5689
这里求 的 次幂(次方)对 取余数的计算，被称为模幂运算，本文会针对以上的式子，根据数据范围提供完全不同的算法来进行讲解，确保正确性的前提下，以求达到时间和空间的平衡；
高端的算法往往只需要采用最朴素的诠释方式。
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];
}
#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 用于判断奇偶性；
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)，相比递归算法减少了一些常数消耗；
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;
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧