首页 > 编程语言 >【算法设计-分治思想】快速幂与龟速乘

【算法设计-分治思想】快速幂与龟速乘

时间:2023-02-27 11:23:54浏览次数:42  
标签:龟速 取模 分治 long 算法 uLL 快速

目录

1. 快速幂

算法原理:

  • 计算 311
    • 311 = (35)2 x 3
    • 35 = (32)2 x 3
    • 32 = 3 x 3
    • 仅需计算 3 次,而非 11 次
  • 计算 310
    • 310 = (35)2
    • 35 = (32)2 x 3
    • 32 = 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 = 3,b = 11
  • 第 1 轮:(11 % 2 == 1)r=1x3=3,b=5,a=32=9
  • 第 2 轮:(5 % 2 == 1)r=3x32=33=27,b=2,a=(32)2=34=81
  • 第 3 轮:(2 % 2 == 0)r 不变,b=1,a=(34)2=38
  • 第 4 轮:(1 % 2 == 1)r=33x38=311,b=0,a=(38)2=316
  • 得到 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;
}

标签:龟速,取模,分治,long,算法,uLL,快速
From: https://www.cnblogs.com/Mount256/p/17159018.html

相关文章

  • 推荐系统[八]算法实践总结V0:腾讯音乐全民K歌推荐系统架构及粗排设计
    1.前言:召回排序流程策略算法简介推荐可分为以下四个流程,分别是召回、粗排、精排以及重排:召回是源头,在某种意义上决定着整个推荐的天花板;粗排是初筛,一般不会上复杂模型......
  • React面试:谈谈虚拟DOM,Diff算法与Key机制
    1.虚拟dom原生的JSDOM操作非常消耗性能,而React把真实原生JSDOM转换成了JavaScript对象。这就是虚拟Dom(VirtualDom)每次数据更新后,重新计算虚拟Dom,并和上一次生成的虚拟......
  • 《分布式技术原理与算法解析》学习笔记Day24
    分布式缓存在计算机领域,缓存是一个非常重要的、用来提升性能的技术。什么是分布式缓存?缓存技术是指用一个更快的存储设备存储一些经常用到的数据,供用户快速访问。分布......
  • 算法题-模拟商场优惠打折
    模拟商场优惠打折:有三种优惠可以用,满减券,打折券和无门槛券满减券:满100减10,满200减20,依次递推打折券:92折,每次打折完向下取整,一次购物只能用一次无门槛券:一张券减5元,多张......
  • 特斯拉自动驾驶算法和模型解读
    特斯拉自动驾驶算法和模型解读特斯拉是一个典型的AI公司,过去一年训练了75000个神经网络,意味着每8分钟就要出一个新的模型,共有281个模型用到了特斯拉的车上。接下来我们分......
  • 数据结构(借鉴408)-高阶算法的应用
    数据结构高阶算法的应用算法分析和解题的一般套路算法解法暴力解:枚举解法可行解:目标解法最优解:缘分解法算法解题得分套路结构体定义算法思想和算法步骤......
  • 算法刷题 Day 56 | ● 583. 两个字符串的删除操作 ● 72. 编辑距离 ● 编辑距离总结
    583.两个字符串的删除操作本题和动态规划:115.不同的子序列相比,其实就是两个字符串都可以删除了,情况虽说复杂一些,但整体思路是不变的。https://programmercarl.com/0......
  • 【算法】排序算法之归并排序
    原文网址:https://zhuanlan.zhihu.com/p/124356219前几回,在前面已经对冒泡排序、直接插入排序、希尔排序、选择排序、快速排序做了说明分析。这回,将对归并排序进行相关说明......
  • 每日算法--2023.2.26
    1.面试题59-II队列的最大值classMaxQueue{//该题的重点在于以o(1)的时间复杂度找到队列中最大的元素,如果只单纯维护当前队列一个最大的值,当该值出队后第二大的值找......
  • 数据结构与算法概述
     一、数据结构与算法简介从广义上讲,数据结构是指一组数据的存储结构。算法是操作数据的一组方法。从狭义上讲,数据结构与算法是指某些著名的数据结构和算法,比如数组、列......