B.Icebound and Sequence(2019河北省大学生程序设计竞赛)

当时一看题面想着用欧拉降幂做(其实不用这样做，因为幂不是一个大整数,貌似算欧拉函数还更耗时间)，做半天也做不出,因为不知道在模运算下怎么处理等比数列分母。 赛后听别人说是个模板题,思想类似快速幂(还是题目做少了QAQ) 解法1,2的分析来自这里：ACdreamers的分析

//B解法1 #include <iostream> #include <string> #include <map> #include<vector> #include<cstdio> #include<cmath> #define ll long long using namespace std; ll mod,q,n; ll fp(ll x,ll y){ ll ret=1; while(y){ if(y&1)ret=ret*x%mod; x=x*x%mod; y/=2; } return ret; } ll sum(ll a,ll n){ if(n==1)return a; ll t=sum(a,n/2); if(n&1){ ll cur=fp(a,n/2+1); t=(t+t*cur%mod)%mod; t=(t+cur)%mod; } else { ll cur=fp(a,n/2); t=(t+t*cur%mod)%mod; } return t; } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%lld%lld%lld",&q,&n,&mod); printf("%lld\n",sum(q,n)); } }

解法2 if(a%b==0)那么有 $$ans=\frac{a}{b}\mathrm{m}\mathrm{o}\mathrm{d}m=a\mathrm{m}\mathrm{o}\mathrm{d}(m\times b)/b$$

//B解法2 #include <iostream> #include <string> #include <map> #include<vector> #include<cstdio> #include<cmath> #define ll long long using namespace std; ll mod,q,n; ll fm(ll x,ll y){//因为mod=mod*(q-1),快速幂容易爆long long所以要加上快速乘 ll ret=0; while(y){ if(y&1)ret=(ret+x)%mod; x=2*x%mod; y/=2; } return ret; } ll fp(ll x,ll y){ ll ret=1; while(y){ if(y&1)ret=fm(ret,x)%mod; x=fm(x,x)%mod; y/=2; } return ret; } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%lld%lld%lld",&q,&n,&mod); mod=(q-1)*mod; ll ans=(fp(q,n+1)-q+mod)%mod/(q-1); printf("%lld\n",ans); } }

其实这个题还有第3个做法就是矩阵快速幂，然而我也没想到

//B解法3 #include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e5+10,N=2; int mod; ll tmp[N][N]; void multi(ll a[][N],ll b[][N],int n) { memset(tmp,0,sizeof tmp); for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) tmp[i][j]+=a[i][k]*b[k][j]%mod; for(int i=0;i<n;i++) for(int j=0;j<n;j++) a[i][j]=tmp[i][j]%mod; } ll res[N][N]; void Pow(ll a[][N],int n) { memset(res,0,sizeof res);//n是幂，N是矩阵大小 for(int i=0;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; } } int main() { int T; cin>>T; while(T--) { int n,q; cin>>q>>n>>mod; ll a[2][2]={1,0,q,q}; Pow(a,n-1); ll ans=1ll*q*res[0][0]%mod+1ll*q*res[1][0]%mod; cout<<ans%mod<<endl; } }