建站公司合肥,做精品课程网站需要啥素材,国内cms排行,西安做网站电话文章目录1. 快速幂2. 龟速乘3. 快速幂取模4. 龟速乘取模5. 快速幂取模优化1. 快速幂
算法原理#xff1a;
计算 311#xff1a; 311 (35)2 x 335 (32)2 x 332 3 x 3仅需计算 3 次#xff0c;而非 11 次 计算 310#xff1a; 310 (35)235 (32)2 x 332 3 x 3仅需计算…
文章目录1. 快速幂2. 龟速乘3. 快速幂取模4. 龟速乘取模5. 快速幂取模优化1. 快速幂
算法原理
计算 311 311 (35)2 x 335 (32)2 x 332 3 x 3仅需计算 3 次而非 11 次 计算 310 310 (35)235 (32)2 x 332 3 x 3仅需计算 3 次而非 10 次
算法思路
若指数是偶数则将底数平方指数除以 2。若指数是奇数则将底数平方指数除以 2再乘上底数。
算法代码
typedef unsigned long long uLL;// 快速幂 a^b
uLL power (uLL a, uLL b){uLL r 1;while (b ! 0){if (b 1) // (b % 2 1)r r * a;b b 1; // (b b / 2)a a * a;}return r;
}举例
初始值a 3b 11第 1 轮11 % 2 1r1x33b5a329第 2 轮5 % 2 1r3x323327b2a(32)23481第 3 轮2 % 2 0r 不变b1a(34)238第 4 轮1 % 2 1r33x38311b0a(38)2316得到 r 33x38 311
2. 龟速乘
算法原理将其中一个乘数分解成 2 的幂次相加。
12 x a 23 x a 21 x a
算法代码
typedef unsigned long long uLL;// 龟速乘 a*b
uLL mul (uLL a, uLL b){uLL r 0;while (b ! 0){if (b 1) // (b % 2 1)r r a;b b 1; // (b b / 2)a a a;}return r;
}3. 快速幂取模
初等数论中有如下公式
(a × b) % m ((a % m) × (b % m)) % m
推广
(a × b × c…) % m ((a % m) × (b % m) × (c % m) × … ) % m
(ab) % m (a × a × a…) % m ((a % m) × (a % m) × (a % m) × … ) % m
算法代码
typedef unsigned long long uLL;// 快速幂取模 (a^b) % p
uLL powerMod (uLL a, uLL b, uLL p){uLL r 1;while (b ! 0){if (b 1) // (b % 2 1)r (r * a) % p;b b 1; // (b b / 2)a (a * a) % p;}return r;
}4. 龟速乘取模
算法原理(a × b) % m ((a % m) × (b % m)) % m
算法代码
// 龟速乘取模 (a*b) % p
uLL mulMod (uLL a, uLL b, uLL p){uLL r 0;while (b ! 0){if (b 1) // (b % 2 1)r (r a) % p;b b 1; // (b b / 2)a (a a) % p;}return r;
}5. 快速幂取模优化
算法原理注意到快速幂取模算法中的相乘操作可能会超出数据范围因此可以将相乘操作转化为龟速乘取模。
原理依然是此公式(a × b) % m ((a % m) × (b % m)) % m其中((a % m) × (b % m))即为龟速乘取模。
算法思路快速幂 龟速乘结合。
// 快速幂取模防止爆炸 (a^b) % p
uLL powerModBig (uLL a, uLL b, uLL p){uLL r 1;while (b ! 0){if (b 1) // (b % 2 1)r mulMod(a, b, p) % p;b b 1; // (b b / 2)a mulMod(a, a, p) % p;}return r;
}
