矩阵快速幂

快速幂

#include<iostream>
using namespace std;int main(){int a, b, p;cin>>a>>b>>p;int res = 1 % p;while(b){if(b & 1) res = 1ll * res * a % p;a = 1ll * a * a % p;b >>= 1;}cout<<res;return 0;
}

斐波那契数列

#include <iostream>
using namespace std;
typedef long long ll;
const int Nmax=10, mod=1e9;struct Matrix
{int n,m;int map[Nmax][Nmax];Matrix(int x,int y){n=x;m=y;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)map[i][j]=0;}Matrix operator * (const Matrix b){Matrix c(n,b.m);if(m==b.n){for(int i=1;i<=c.n;i++)for(int k=1;k<=m;k++)for(int j=1;j<=c.m;j++)c.map[i][j]=(c.map[i][j]+(map[i][k]*b.map[k][j])%mod)%mod;return c;}printf("error!!!!!!!!!!!!!!\n");   return c;}Matrix operator + (const Matrix b){Matrix c(n,m);if(m==b.m && n==b.n){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)c.map[i][j]=(map[i][j]+b.map[i][j])%mod;return c;}printf("error!!!!!!!!!!!!!!\n");   return c;}void show(){printf("n:%d m:%d\n",n,m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)printf("%4d%c",map[i][j],j==m?'\n':' ');}
};
int a,b,n;
int work()
{Matrix base(2,2);base.map[1][1]=a,base.map[1][2]=b;base.map[2][1]=1;//base.show();Matrix ans(2,2);ans.map[1][1]=1,ans.map[2][2]=1;if(n<=2)return 0*printf("1\n");n-=2;while(n){if(n&1)ans=ans*base;base=base*base;n>>=1;}Matrix now(2,1);now.map[1][1]=now.map[2][1]=1;//ans.show();ans=ans*now;//now.show();printf("%d\n",ans.map[1][1]);return 0;
}
int main()
{while(~scanf("%d%d%d",&a,&b,&n)){if(!a && !b && !n)break;work(); }return 0;
}

a ^ n + b ^ n

#include <iostream>
using namespace std;
typedef unsigned long long ll;
const int Nmax=10;
ll a,b,n;struct Matrix
{int n,m;ll map[Nmax][Nmax];Matrix(int x,int y){n=x;m=y;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)map[i][j]=0LLu;}Matrix operator * (const Matrix b){Matrix c(n,b.m);if(m==b.n){for(int i=1;i<=c.n;i++)for(int k=1;k<=m;k++)for(int j=1;j<=c.m;j++)c.map[i][j]=c.map[i][j]+map[i][k]*b.map[k][j];return c;}printf("error!!!!!!!!!!!!!!\n");   return c;}Matrix operator + (const Matrix b){Matrix c(n,m);if(m==b.m && n==b.n){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)c.map[i][j]=map[i][j]+b.map[i][j];return c;}printf("error!!!!!!!!!!!!!!\n");   return c;}void show(){printf("n:%d m:%d\n",n,m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)printf("%4llu%c",map[i][j],j==m?'\n':' ');}
};ll work()
{Matrix base(2,2);base.map[1][1]=a,base.map[1][2]=-b;base.map[2][1]=1LLu;//base.show();Matrix ans(2,2);ans.map[1][1]=1LLu,ans.map[2][2]=1LLu;ll newa=a*a-2LLu*b;if(n==2)return newa;if(n==1)return a;if(n==0)return 2LLu;n-=2LLu;while(n){if(n&1LLu)ans=ans*base;base=base*base;n>>=1;}Matrix now(2,1);now.map[1][1]=newa;now.map[2][1]=a;//ans.show();ans=ans*now;//now.show();return ans.map[1][1];
}
int main()
{while(~scanf("%llu%llu%llu",&a,&b,&n)){if(!a && !b && !n)break;printf("%llu\n",work());}return 0;
}