Fast Power

╰+攻爆jí腚メ 2021-12-09 14:53 191阅读 0赞

一、

整数：求a^n，把n化为2\*（k1+k2+..+km)；

矩阵：注意矩阵乘法。

复杂度：O(logn)

tip：取了模（根据题目要求）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 #define mem(a) memset(a,0,sizeof(a))
     3 #define ll long long
     4 using namespace std;
     5 ll mod=1e9;
     6 ll quickpow(ll a,ll n){
     7     ll ans=1;
     8     while(n){
     9         if(n&1)
    10             ans=(ans*a)%mod; //取模
    11         n>>=1;
    12         a=(a*a)%mod;
    13     }
    14     return  ans%mod;
    15 }
    16 int main(){
    17    cout<<quickpow(2,19);
    18    return 0;
    19 }

整数

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 #define mem(a) memset(a,0,sizeof(a))
     3 #define ll long long
     4 const int N=1e6+5;
     5 using namespace std;
     6 ll mod=1e9;
     7 struct matrix{
     8   int m[N][N];
     9 };
    10 matrix mat_multi(matrix a, matrix b){
    11    matrix ans;
    12    for(int i=0;i<N;i++){
    13     for(int j=0;j<N;j++){
    14         ans.m[i][j]=0;
    15         for(int k=0;k<N;k++){
    16             ans.m[i][j]+=(a.m[i][k]%mod*b.m[k][j]%mod)%mod;
    17             ans.m[i][j]%=mod;
    18         }
    19     }
    20    }
    21    return ans;
    22 }
    23 matrix quickpow(matrix a,ll n){
    24     matrix ans;
    25     for(int i=0;i<N;i++){
    26         for(int j=0;j<N;j++){
    27             if(i==j) ans.m[i][j]=1;
    28             else ans.m[i][j]=0; 
    29     //初始化为单位矩阵，类比整型时的1；单位矩阵*矩阵A=矩阵A
    30         }
    31     }
    32     while(n!=0){
    33         if(n&1)
    34             ans=mat_multi(a,ans); 
    35         n>>=1;
    36         a=mat_multi(a,a);
    37     }
    38     return  ans;
    39 }

矩阵

二、题目

①基础

（1）[http://noi.openjudge.cn/ch0204/2991/][http_noi.openjudge.cn_ch0204_2991]

关键是循环节

tips：string->int：m=atoi(n.c\_str());

去字符串：substr(起始，长度）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 #define mem(a) memset(a,0,sizeof(a))
     3 #define ll long long
     4 #define inf 0x3f3f3f3f
     5 const int N=1e6+5;
     6 using namespace std;
     7 ll mod=1e4;
     8 ll Mod=500;
     9 ll ans[205];
    10 ll quickpow(ll a,ll n){
    11    ll ans=1;
    12    while(n){
    13       if(n&1) ans=(ans*a)%mod;
    14       n>>=1;
    15       a=(a*a)%mod;
    16    }
    17    return ans%mod;
    18 }
    19 int main(){
    20    int k;
    21 
    22    string n;
    23    cin>>k;
    24    while(k--){
    25     cin>>n;
    26     int len=n.size();
    27     int m;
    28     if(len>5){
    29         string n1=n.substr(len-4,4); //起始，长度
    30         m=atoi(n1.c_str()); //返回一个const *char,内容相同
    31     }
    32     else
    33     m=atoi(n.c_str());
    34     cout<<quickpow(2011,m%Mod)<<endl;
    35    }
    36    return 0;
    37 }

2991：2011

转载于:https://www.cnblogs.com/XXrll/p/11104978.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211209/eea29fded8cd4df8a6323f8c7e537a64.png
[http_noi.openjudge.cn_ch0204_2991]: http://noi.openjudge.cn/ch0204/2991/