第二季企业网站开发,wordpress内核,购物网站建设合同,公司网站乱码List 快速幂与快速乘法 ListKnowledge快速幂 原理code快速乘法 原理codeKnowledge 快速幂 原理 a^b%p 采用二进制得思想#xff0c;将b转化为二进制数。 b c02^0c12^1c22^2c32^3……cn2^n a^b a^(a12^0)a^(c12^1)……a^(cn2^n) 所以我们可以在log(b)的时间内求出a^(2^0)… List 快速幂与快速乘法 ListKnowledge快速幂 原理code快速乘法 原理code Knowledge 快速幂 原理 a^b%p 采用二进制得思想将b转化为二进制数。 b c0×2^0c1×2^1c2×2^2c3×2^3……cn×2^n a^b a^(a1×2^0)×a^(c1×2^1)×……×a^(cn×2^n) 所以我们可以在log(b)的时间内求出a^(2^0)a^(2^1)……a^(2^n)同时c也可得到故复杂度O(log(b)) eg.a^11 11的二进制是1011 11 2³×1 2²×0 2¹×1 2º×1 code int quick_pow(int a,int b,int p){int w1;while(b){if(b1)w(w*a)%p;b1;a(a*a)%p;}return w;
} 快速乘法 原理 a*b%p 与快速幂类似 a*ba*(c0×2^0c1×2^1c2×2^2c3×2^3……cn×2^n) 在log(b)的时间内可以求出a*2^i code int quick_mul(int a,int b,int p){int w0;while(b){if(b1)w(wa)%p;b1;a(aa)%p;}return w;
} 转载于:https://www.cnblogs.com/YJinpeng/p/5907204.html
