快速幂运算

发表于
字数统计: 206 | 阅读时长 ≈ 1

快速幂是O(logN)的简单算法

​ 直接贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;

//取模运算对于加法和乘法不会改变尾数的值
//这里主要是为了防止爆精度
//快速幂复杂度是O(logN)

 ll qpow(ll num,ll pow)
{
    ll ret=1;
    if(pow==0) return ret;
    while(pow)
    {
        if(pow&1) ret=(ret*num)%INF;      
        //如果出现了对应的幂次，则乘到结果中去；
        //举个例子5^6;6=110二进制；故5^6=[5^(2^2)]*(5^2);而没有5^(2^0)
        num=(num*num)%INF;                  
        //第一次为5；第二次为5^2;第三次为5^3
        pow=pow>>1;                         
        //幂次右移运算
    }
    return ret;
}
int main()
{
    ll n,i;
    while(cin>>n>>i)
    cout<<qpow(n%INF,i)<<endl;
    system("pause");
    return 0;
}