快速乘:
long long quick(long long a,long long b,long long c)
{
long long ans=0;
while(b)
{
if(b&1) ans=(ans+a)%c;
b>>=1;
a=(a+a)%c;
}
return ans;
}
快速幂:
long long B_quick(long long a,long long b,long long c)
{
int ans=1;
a=a%c;
while(b)
{
if(b&1) ans=(ans*a)%c;
b>>=1;
a=(a*a)%c;
}
return ans;
}
矩阵快速幂:
矩阵快速幂和快速幂相同,只不过把数字换成了矩阵。
const int N=10;
const long long mod=1e9;
void quick(long long ans[N][N],long long B[N][N],long long n)
{
for(int i=0;i<N;i++) ans[i][i]=1;
while(n)
{
if(n&1) mul(ans,B,mod);
mul(B,B,mod);
n>>=1;
}
}
void mul(long long C[N][N],long long D[N][N],long long mod)
{
long long sum[N][N]={0};
int i,j,k;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
for(k=0;k<N;k++)
sum[i][j]=(sum[i][j]+C[i][k]*D[k][j]%mod);
for(i=0;i<N;i++)
for(j=0;j<N;j++)
C[i][j]=sum[i][j];
}
十进制快速幂:
利用二进制的性质有快速幂,当然也可以利用十进制进行快速幂。当指数非常大时,需要通过十进制快速幂对数据进行过渡处理,再利用二进制快速幂求解。
const long long mod=1e9;
long long D_quick(long long a,string b,long long mod)
{
long long sum=a,ans=1;
for(int i=b.size()-1;i>=0;i--)
{
ans=ans*B_quick(sum,b[i]-'0')%mod;
sum=B_quick(sum,10);
}
return ans;
}