旗袍网站架构,wordpress首页加载慢,免费建立公司网站,百度云网盘快速幂 快速幂是我们经常用到的一种算法#xff0c;快速幂顾名思义就是快速的幂运算。我们在很多题目中都会遇到幂运算#xff0c;但是在指数很大的时候#xff0c;我们如果用for或者是pow就会超时#xff0c;这时候就用到了快速幂。 快速幂的原理就是#xff0c;当求b^p的…快速幂 快速幂是我们经常用到的一种算法快速幂顾名思义就是快速的幂运算。我们在很多题目中都会遇到幂运算但是在指数很大的时候我们如果用for或者是pow就会超时这时候就用到了快速幂。 快速幂的原理就是当求b^p的时候如果p是一个奇数那么我们就可以把它拆成(b^2)^(p/2)*b因此每次判断一下是直接乘还是拆开就可以了。 洛谷模板链接https://www.luogu.org/problemnew/show/P1226 下面是代码 #includebits/stdc.h
using namespace std;
long long b,p,k;
void ksm(){long long ans1,ab,bbb,ppp;while(p){if(p1) ansans*a%k; //判断要不要拆开p1; //p除以2aa*a%k;}printf(%lld^%lld mod %lld%lld,bb,pp,k,ans%k);
}
int main(){scanf(%lld%lld%lld,b,p,k);ksm();return 0;
} 矩阵快速幂 矩阵快速幂顾名思义就是把快速幂的整数换成矩阵要学习矩阵快速幂就要先知道矩阵的乘法规则。矩阵的乘法规则由下图所示 注意两个矩阵可以做乘法的条件是矩阵A的大小是N*M矩阵B的大小是M*K这样的两个矩阵相乘得到矩阵C的大小是N*K。通俗的说就是第一个矩阵的列数等于另一个矩阵的行数 矩阵的乘法有几个性质是很重要的必须记住不要搞混①矩阵乘法满足乘法结合律 ②矩阵乘法满足乘法分配律包括左分配律和右分配律左分配律是C*(AB)CACB右分配律是(AB)*CACBC ③矩阵乘法不满足乘法交换律例AC!CA。 矩阵乘法的时间复杂度是O(NMK)的下面是矩阵乘法的代码 for(i1;in;i)for(j1;jm;j)for(l1;lk;l)c[i][l]a[i][j]*b[j][l]; 注意在做矩阵乘法的时候最好是按照我上面代码的循环顺序计算因为如果你改变了循环顺序速度就会变慢如果你不相信的话可以去试一试这是因为按照我代码的顺序在计算一部分值之前他的原值已经存在缓存中了这样的话是比从内存中读取快的而改变顺序的话就会从内存中调用就会变慢了。 学会了矩阵乘法矩阵快速幂就很轻松了。因为矩阵快速幂和快速幂的区别就在于一个是整数的次方运算一个是矩阵的次方运算。但需要注意的是在矩阵相乘的时候要存在第三方数组中这样才不会影响矩阵的值。 洛谷模板链接https://www.luogu.org/problemnew/show/P3390 下面是AC代码 #includebits/stdc.h
using namespace std;
typedef long long ll;
const int M1000;
const ll mod 1e97;
ll n,k,a[M][M],b[M][M],c[M][M];
void jz(int x){register int i,j,l;if(x1){for(i1;in;i)for(j1;jn;j)for(l1;ln;l)c[i][l](c[i][l]a[i][j]*b[j][l]%mod)%mod;for(i1;in;i)for(j1;jn;j)b[i][j]c[i][j];memset(c,0,sizeof c);}else{for(i1;in;i)for(j1;jn;j)for(l1;ln;l)c[i][l](c[i][l]a[i][j]*a[j][l]%mod)%mod;for(i1;in;i)for(j1;jn;j)a[i][j]c[i][j];memset(c,0,sizeof c); //记住每次要清空}
}
void ksm(){while(k){if(k 1) jz(1);k1;jz(2);}
}
int main(){register int i,j;scanf(%lld,n);scanf(%lld,k);for(i1;in;i)for(j1;jn;j)scanf(%lld,a[i][j]),b[i][j]a[i][j];--k; //因为在上一句中在答案中已经有了矩阵A的一次方ksm();for(i1;in;i){for(j1;jn;j)printf(%lld ,b[i][j]);printf(\n);}return 0;
} 快速乘法 快速乘法和快速幂的思想差不多KSM是把a^p的p二进制分解而快速乘法是把a*b的b分解一般和KSM配套食用。当KSM%p会超范围的时候也就是取模之前就会乘爆就要用到快速乘法。快速乘法就是把乘法改成加法这样一步一步的取模就不会出现乘爆的问题了。 因为没有找到例题这里直接附上代码 typedef long long ll;
ll ksmul(ll x,ll y,int p){ //x*y%pll ans0;while(y){if(y 1) ans(ansy)%p;y1;x(xx)%p;}return ans;
} 转载于:https://www.cnblogs.com/Glacier-elk/p/9489655.html
