快速幂，矩阵快速幂，加塞gcd（我是FW（高呼））

快来打我* 2022-02-04 12:53 172阅读 0赞

ll gcd(ll a,ll b)\{return b==0?a:gcd(b,a%b);\}  
快速幂

应用：求a^b%mod

ll power(ll a,ll b)///a是底数，b是次幂
    {
     ll ans=1;
     for(;b!=0;b/=2)
     {
      if(b&1) ans=(long long)ans*a%mod;
      a=(long long)a*a%mod;
     }
     return ans;
    }

///快速幂版本\*2

int pow(int x,int n)
    {
         
         if(n==1)
            return x；
           if(n%2==0)
        {
            int h=pow(x,n/2);
            return h*h;
        }
        int h=pow(x,n/2);
        return h*h*x;
    }

牛客有一道快速幂模板进阶题  
链接：https://ac.nowcoder.com/acm/contest/3800/A  
本质上和快速幂是没区别的 但是我蠢了就是没想到  
这里面的a b mod 的范围都是1e18 所以普通的快速幂 会出现爆ll的情况  
函数中的 ans*a 与 a*a这两行代码

于是就有了一个快速幂的变种问题  
a*b%c  
相当于  
a*20%c+a\*21%c+a\*2^2%c+…  
大概就是这样 ，然后套快速幂的板子就能过这题了

ll pow1(ll a,ll b,ll c)///a*b%c
    {
        ll ans=0;
        while(b)
        {
            if(b&1)
            {
                ans+=a%c;
                ans%=c;
            }
            b/=2;
            a=a*2%c;
        }
        return ans;
    }

~~~~~~~~~~~
    
    ~~~~~~~~~~~~~~~~~~~
    ///矩阵乘法
    2*2矩阵自乘
    [a11 a12]* [a11 a12] = [a11*a11+a21*a12    a12*a11+a22*a12]
    [a21 a22]   [a21 a22]     [a11*a21+a21*a22    a12*a21+a22*a22]
    找出递推公式，然后对矩阵使用快速幂思想从而直接得到某一项的值
    矩阵快速幂自写的板子
    
        ///递推式是k*k矩阵
        ///假设递推矩阵已知为 ditui[k+1][k+1];
        ///矩阵乘法不可交换
        int ditui[k+1][k+1];
        int power(int n)
        {
            int ans[k+1][k+1];
            for(int i=1;i<=k;i++)
                for(int j=1;j<=k;j++)
                if(i==k)
                ans[i][j]=1;
            else 
                ans[i][j]=0;
            for(;n!=0;n/=2)
            {
                if(n&1==1) 
                {int h[k+1][k+1]={0};
                    for(int i=1;i<=k;i++)
                        for(int j=1;j<=k;j++)
                        for(int g=1;g<=n;g++)
                            h[i][j]+=ans[i][g]*ditui[g][j];
                    for(int i=1;i<=k;i++)
                        for(int j=1;j<=k;j++)
                        ans[i][j]=h[i][j];
                }
                int h[k+1][k+1]={0};
                for(int i=1;i<=k;i++)
                        for(int j=1;j<=k;j++)
                        for(int g=1;g<=n;g++)
                            h[i][j]+=ditui[i][g]*ditui[g][j];
                    for(int i=1;i<=k;i++)
                        for(int j=1;j<=k;j++)
                        ditui[i][j]=h[i][j];
            }
            return ans[1][1];
        }
        
    网上的用结构体存的方式分俩函数  看起来会清爽很多  但懂了原理 板子爱怎么写怎么写咯