快速幂

发表于

摸一发快速幂

标准快速幂的原理就是把指数拆成二进制减少乘法次数。直接放代码实现了：

1
2
3
4
5
6
7
8
9
10
int qpow(int a,int b){
    int ans=1;
        while(b){
        if(b&1)
        　　ans*=a;
        a*=a;
        b>>=1;
　 }
    return ans;
}

显然运算量减少了许多。在大指数幂的时候尤为突出。//其实这样能不能做一个推广？在大指数幂的时候用十进制来乘呢？算术运算次数小应该能弥补逻辑运算量太大的不足？

当然在实操中还会用到取模这个操作。我们可以根本不去考虑乘方运算取模法则：

1
2
3
4
5
6
7
8
9
10
11
12
int mi(int a,int b)
{
    int ans=1;
    a%=mod;
    while (b)
    {
        if (b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}

同理我们可以将加法分解为快速加法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ll multi(ll a,ll b,ll p) 
{ 
    a=a%p; 
    b=b%p; 
    ll ans=0; 
    while(b>0) 
    {  
        if(b&1==1)    
        {             
            ans+=a;     
            ans%=p;    
        }  
        b=b>>1;  
        a=a+a;  
        a=a%p; 
    }    
    return ans; 
}

这算是简单的快速幂变形了。然鹅还有一个大boss：

矩阵快速幂

矩阵运算的朴素算法如下：

1
2
3
4
5
6
7
8
9
10
const int N=100;
int c[N][N];
void multi(int a[][N],int b[][N],int n)
{
    memset(c,0,sizeof c);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
        c[i][j]+=a[i][k]*b[k][j];
}

显然此算法的复杂度是O(n^3)。

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
const int N=10;
int tmp[N][N];
void multi(int a[][N],int b[][N],int n)
{
    memset(tmp,0,sizeof tmp);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
        tmp[i][j]+=a[i][k]*b[k][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        a[i][j]=tmp[i][j];
}
int res[N][N];
void Pow(int a[][N],int n)
{
    memset(res,0,sizeof res);
    for(int i=1;i<=n;i++) res[i][i]=1;
    while(n)
    {
        if(n&1)
            multi(res,a,n);//res=res*a;复制直接在multi里面实现了；
        multi(a,a,n);//a=a*a
        n>>=1;
    }
}

res数组初始化就等同于单位矩阵E,最终算出的结果是一个res矩阵。

铜牌爷的写法

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
34
35
36
37
38
struct matrix 
{ 
    ll v[2][2]; 
    matrix() 
    {  
    memset(v,0,sizeof(v)); 
    } 
    matrix operator *(matrix &t) 
    {  
        matrix res;  
        memset(res.v,0,sizeof(res.v)); 
        for(int i=0; i<2; i++)   
            for(int j=0; j<2; j++)    
                for(int k=0; k<2; k++)    
                {     
                    res.v[i][j]+=v[i][k]*t.v[k][j];     
                    res.v[i][j]%=MOD;    
                }  
         return res; 
    } 
}; 
matrix power(matrix a,int b) 
    {
    matrix ans;
    memset(ans.v,0,sizeof(ans.v));
    ans.v[0][0]=1;
    ans.v[1][1]=1;
    while(b>0) 
    {
        if(b%2==1)
        {
            ans*=a;
        }
        b=b>>1;
        a=a*a;
    } 
    return ans;
}

至于应用。。今天就摸了。。改日
可以先看看dalao的应用：

http://blog.csdn.net/wust_zzwh/article/details/52058209