作者：李狗嗨

链接：https://www.zhihu.com/question/26097157/answer/265975884

来源：知乎

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 

数学的基本运算可分为三个等级。第一级为加、减运算，虽然加减法的概念在公元前20世纪的古埃及数学家艾哈迈斯(Ahmes)的纸草书中就有体现，但今天的加号“+”和减号“-”，最早有史料记载的，是在15世纪末的德国人的手稿中，现保存于德国德累斯顿(Dresden)图书馆[1]。

后来，人们发现在遇到“连加”或“连减”时，加减法的效率很低，于是就发明了第二级运算——乘法和除法以及与此对应的乘号和除号。在西方，“×”被称为“圣安德鲁斜十字(St. Andrew’s Cross)”。安德鲁是耶稣的12门徒之一，由于其被钉死在斜十字架上，因此，斜十字架也成为圣安德鲁斜十字。现代意义上的“×”号最先出自于1631年英国数学家奥特雷德(William Oughtred)的《数学之钥》中。

1698年，莱布尼兹(Gottfried Wilhelm Leibniz)[2]在其给瑞士数学家雅各比·伯努利(Jacob Bernoulli)的信件中首次使用“·”表示乘法，以此来避免乘号“×”和字母“X”的混淆。不过，后来在向量代数中，用“·”表示“数量积”或“内积”，而“×”则表示“向量积”或“外积”，这就算是另一种区分方法了。

 



Gottfried Wilhelm Leibniz (1646-1716) (图片来源: Wikipedia)

 

今天用的除号“÷”称为“雷恩记号”。它是瑞士数学家雷恩(Rahn)在其1659年出版的一本代数书中首先使用，在1688年，这本书被译成英文，这个符号也随之通用起来。

但人们还不满足，因为人们遇到了“连乘”和“连除”，即“乘方”。而且，乘方有两种逆运算，分别是“开方”和“对数”。这是第三级运算与加减乘除的不同之处。

法国数学家笛卡尔(Descartes)在1637年定义了现代乘方符号，即在字母或数字的右上角用小的阿拉伯数字表示指数。1732年卢贝(Loubere)首次使用根号来表示开方，并逐渐流行起来。

“开方”的诞生似乎顺理成章，但是乘方的另一种逆运算——“对数”，就有些“难产”了。

斯蒂菲尔(Michael Stifel)[3]是德国德国哥尼斯堡大学的数学讲师，1544年，他写了一本书叫《整数的算术》，在这本书中他应用“一一对应”的方法几乎造就了一座数学丰碑。

 



Michael Stifel (1487-1567) (图片来源: Wikipedia)

斯蒂菲尔在书中写道：“关于整数的这些奇妙性质，可以写成整本整本的书！”下面就是他书中列出的两列数字：

 



 

可以看出，上一列其实就是通项公式为  的等比数列（  为整数），他称其为“原数”；下一列则是一个由整数构成的等差数列，他称其为“代表数”，德语是Exponent，也可译为“代言人”。

他发现，两个“原数”相乘等于“代表数”相加后得到的“代表数”所对应的“原数”；“原数”相除等于“代表数”相减后得到的“代表数”所对应的“原数”。即，利用这两列数可以把较为复杂的乘除法变成较为简单的加减法。

其实，在我们看来，这个结论没有什么神奇之处，因为所谓的“代表数”其实就是“原数”以2为底的对数。但是在当时，这种计算方法思想是开创性的。

不过遗憾的是，在斯蒂菲尔的那个年代还没有分数指数的概念，因此在处理指数不是整数时遇到了巨大的阻力，最后，他放弃了对这种计算方法的进一步研究，而只是停留在了整数上。不过，斯蒂菲尔也并非全然无功，他的前驱性工作，成为纳皮尔发明对数的“巨人肩膀”。

约翰·纳皮尔(John Napier)[4]是苏格兰数学家、物理学家兼天文学家。1614年，其在爱丁堡出版了《奇妙的对数定律说明书》中提出了对数的概念。

 



John Napier (1550-1617) (图片来源: Wikipedia)

"看起来在数学实践中，最麻烦的莫过于大数字的乘法、除法、开平方和开立方，计算起来特别费事又伤脑筋，于是我开始构思有什么巧妙好用的方法可以解决这些问题。"

--约翰·纳皮尔，《奇妙的对数定律说明书》[5]

作为数学家、物理学家兼天文学家，他在计算各种行星轨道数据时，也被浩瀚的计算量所折磨，因此很痛恨这些乏味的重复性工作。为了解决这一问题，他用了20年的时间，进行了数百万次的计算，发明了对数和对数表，听起来很矛盾，一个不想做重复工作的人结果做了20年重复性工作。但是，他的努力确实为后人减少了大量的重复性工作，大大减少了数学家、天文学家的计算量，由此可见，这在天文学界算得上是一项伟大的发明了，看看名人们对其的评价就能看出其重要性[6]。

“对数的发明、解析几何的创始和微积分的建立是17世纪数学的三大成就。”

——恩格斯

“对数的发现，因其节省劳力而延长了天文学家的寿命。”

——拉普拉斯

“给我空间、时间及对数，我就可以创造一个宇宙。”

——伽利略

对数使得手算变得简单而且快多了，也因此为后来许多科学进步开启了大门。那么如何理解对数？一个直观的解释是：对数指的是到达某一数量所需要的时间。这里先介绍自然对数。即以  为底的对数。



 

例如，有一个土豪投资的项目正好满足年利率为100%的连续复利。但是这个土豪小学文化，数学水平也就加减乘除，假设你是这个项目的负责人，想劝说土豪再多投资，如果跟他说什么连续复利、什么100%、什么指数增长，土豪听不懂啊，你再这么说下去感觉在欺负人啊！土豪就发话了：“别整那些没用的，你就告诉我，我的钱啥时候能涨到10倍，100倍，1000倍？”你有些发懵了，一般人不怎么问啊，不都是问一年后是多少，两年后是多少之类的吗？所以这里的问题就是知道时间求数量的逆向问题——知道数量求时间。土豪就是土豪，有的是钱，他只想从翻倍时间的长短来判断哪项投资赚得快。因此，这里就要用到对数，在这样一个年利率为100%的连续复利增长模型下，如果你想得涨到你本金10倍，你需要等待的时间其实就是  年，到100倍所需时间就是  年，到1000倍所需时间就是  年。

与 

 和  好像是孪生一对，  表示单位数量经过x个单位时间增长后的数量（在单位时间增长率为100%的连续复利情况下）。那么在单位时间增长率为50%的连续复利情况下，增长4年和单位时间增长率为100%的连续复利情况下增长2年是一样的。因为  。所以，可以看出，不管利率是多少，通用的连续复利模型  都可以描述。

 表示单位数量增长到  个单位数量所需要的时间（在单位时间增长率为100%的连续复利情况下）。  正好与  相反，  表示输入时间得到数量，  表示输入数量计算达到这么多数量所需时间。



 

自然对数的计算

有人可能会觉得对数这种算法很奇怪，不知道为什么它能够将乘法转变为加法，把除法转化为减法，但如果掌握其“数学内涵”的话，就好理解了。

先看  ，它是多少呢？我们都知道答案是0，因为其数学内涵是：单位数量增长到单位数量的1倍时所需要的时间，因为现在就已经是现在数量的1倍了，所以无需再给予时间让它增长了。

那么，如果是分数呢？例如，得到现在数量的1/2需要多久。我们知道ln(2)表示在单位时间增长率为100%的连续复利情况下翻倍所需要的时间。那我们取反，就得到了退回现在的一半所需要的时间（如果是等待所花费的时间为正，如果是“时光倒流”的话，时间则为负，是不是很直观？！）。因此 

那么能不能对负数取对数呢？答案是否定的，因为一个给定的数量不能增长为一个负数也无法退回成为一个负数，再怎么等待下去或者再怎么“时光倒流”，这种情况也不可能发生，所以没有定义。



 

为了增长到30倍，我们可以等ln(30)个单位时间，也可以先等增长3倍所需要的时间ln(3)再等个增长10倍所需要的时间ln(10)，效果是一样的。因为在增长率不变的连续复利情况下，给定一个初始值，那么增长到初始值的x倍所需要的时间是一定的，与初始值的大小并没有任何关系。即  。

那么  呢，意味着计算增长到现在的5倍所需时间减去以5倍为基数退回到其1/3所需时间。所以有  。

相乘增长量=时间相加

相除增长量=时间相减

但是对于增长率不是100% 的连续复利模型呢？

其实同样适用。

例如  可以看为是在单位时间利率100%连续复利情况下变为原来的30倍所需要的时间为3.4个单位时间。

由于  =  即 

当我们计算单位时间利率为5%，增长到30倍所需时间时。其实只要保证  即可。即  ，所以 

72法则

这是一种快捷算法，因为实际中银行的利率不可能是100% ，但是我们经常想知道本金到底什么时候能够翻倍。而对于利率为100% 的连续复利，如果要翻倍就需要ln(2)=0.693个单位时间。

那么对于小利率呢，为了方便计算现将利率乘以100，但注意是百分数。那么0.693也要乘以100，等于69.3。

由  ，可知 

但是69.3并不太好分，所以我们取一个相近的，72，因为其可以被2、3、4、6、8整除。因此，翻倍所需时间大约是  ，这就是“72”法则。当然，如果想计算增长到3倍的话那就是“110”法则了。

1.大数运算
（整型或浮点型）大数加减乘除、阶乘

以下，都为人工竖式思路

加法：模拟人工竖式，标记进位

减法：先判断大的，模拟人工竖式，标记借位

乘法：模拟竖式，从低位向高位乘，再进行各位的加法及进位

除法：

取模：模拟人工竖式，被除数-除数的10^n的倍数，n即商的所在位

取余：如上

阶乘：

求阶乘位数：lg(N!) = [lg(N*(N-1)*(N-2)*...*3*2*1)]+1= [lgN+lg(N-1)+lg(N-2)+...+lg3+lg2+lg1]+1

求阶乘：进位，一个个相乘，a[]标记每一位的结果，若有进位，a[]数组对应位置相加

注意：

若为浮点数计算，要先找到小数点位置进行小数点对齐

常见大数运算方法还有分治法等，分治法把数字分成一块一块的，然后再进行整合
2.二维数组二分查找
该排序的二维数组a[m][n]特点为每行数据是有序的，每列数据是有序的

思路为：从左下角第一个数开始查找，若更大，则向上查找，若更小，则向右查找，最大时间复杂度，也只是O（m+n）
3.1TB数据如何使用32GB内存排序
采用外排序：

1TB分为40块，每块25GB，留一些系统空间
25GB读入内存，进行内部排序（如：快排）
把排好的数据存回磁盘
循环排序40块
从40块分别读取25GB/40入内存
40路合并，并将合并结合临时存储于2GB基于内存内存的输出缓冲区，写满2GB时，写入磁盘上最终文件，并清空输出缓冲区

4.找出海量数据中最大的k个数

小根堆

建一个大小为k的小根堆，遍历数据，前k个数先建堆，之后每当后面有数比k大，则替换根节点并调整堆
分治法

将数据分块，每块找到最大的k个数，再继续分块找新块的最大的k个数，重复步骤即可

5.如何让快排稳定

设置双标志位，不在乎空间的话，把原数组的元素包装一下，变成（元素，下标）的形式，比较时若元素相等，比较下标，排序完成后拆开就好了
可以用另外一个和待排序一样长度的辅助数组。对待排序数组两次扫描，第一次从下标0到len把比tmp小的依次从左到右一直放到辅助数组里。然后第二次扫描待排序数组从下标len到0,把大于等于tmp的依次从右到左放到辅助数组里。最后拷贝辅助数组到原数组，这样应该就是稳定的partition了。当然第一次扫描需要记录mid的位置，而且选择比较的tmp也要数组的第一个也就是low下标的数

6.找到有序数组中唯一相加为0的一对数
和快排的思路有些类似，快排比较的是两个数的大小，这个则是比较两个数绝对值，若绝对值大的，基准位置向左或向右移动
7.找到1-100中不存在于数组a[99]的数
给一个临时变量，依次异或1-100，再去异或数组元素，最终得到的结果即为不存在的数
8.链表相关问题

快慢指针法：给定一个快指针fast=fast->next->next，一个慢指针low=low->nest

解决问题：

找链表中是否有环：

如果有环，则一定会相遇

找链表中间节点：

若fast->nest为NULL，则low所在位置即中间节点

找倒数第k个节点：

设有两个指针 low，fast，fast 先走 k - 1 步，再使两个指针同时走，当 fast -> next 指向空时，返回 low即倒数第 k 个结点
cur，prev，next指针法：也叫三指针法，cur、prev指向链表头部，next指向头部的next

解决问题：

反转链表：

给定三个指针 n1，n2，n3，n1 指向头节点，n2 指向头-> next，n3 指向头-> next -> next ,使 next 指向 prev ,即 n2 -> next = n1，n3 始终向后移动，直到 n3 指向空，即 n1 和 n2 改变指针所指方向， n3 为指针方向改变的位置

删除重复节点：

给三个指针 cur，next，prev，cur 指向第一个结点，若后移过程与 next 相等，删除 next 后 cur 再后移，直至 cur 与 next 不相等时，删除 cur ，cur 后移，prev 后移，next 后移，重新链接 prev 和新 cur，若后移过程中，cur 与 next 不相等，next、cur、prev 后移

用中国科学技术大学数学系七八年级学生史丰收创造的快速计算法，可以进
行任意位数的加、减、乘、除、乘方、开方、分数、三角函数、对数的运算，快
速、准确。算法是从高位数算起。史丰收总结了二十九句口诀，用来表示一位数
乘多位数的进位规律，掌握了这些口诀和一些具体法则，就能进行快速运算。
　　二十九句口诀如下：
　　乘数为２时，口诀为：满５进１；
　　乘数为３时，口诀为：超３进１，超６进２；
　　乘数为４时，口诀为：满２５进１，满５０进２，满７５进３；
　　乘数为５时，口诀为：满２进１，满４进２，满６进３，满８进４；
　　乘数为６时，口诀为：超１６进１，超３进２，满５进３，超６进４，超８
３进５；
　　乘数为７时，口诀是：超１４２８５７进１，超２８５７１４进２，超４２
８５７１进３，超５７１４２８进４，超７１４２８５进５，超８５７１４２进
６；
　　乘数为８时，口诀是：满１２５进１，满２５进２，满３７５进３，满５进
４，满６２５进５，满７５进６，满８７５进７；
　　乘数为９时，口诀为：超１进１，超２进２，……超８进８；
　　口诀中所说的“满”是“大于”或“等于”的意思。“超”是“大于”的意
思。数字上面有一点的，代表循环小数，如“３”，读做“循环３”，也就是小
数“３”的不断重复。“６”读做“循环６”，也就是小数“６”的不断重复。
……
　　计算时，乘数是几就按几的进位规律进行运算，运算法则是：被乘数首位前
补“０”，从高位起逐位相乘，按“本个”加“后进”，满“１０”只取和的个
位数的方法进行计算。“本个”就是九九表中的个位数，“后进”就是后位的进
位数。
　　运用口诀进行计算的举例：
　　３３８６７×３＝？
　　首先在被乘数首位补“０”，就变成：０３３８６７乘以３。
　　运算方法如下：
　　０３３８６７乘以３，得积１０１６０１。
　　积的第一位“１”是这样算得的：０乘以３得０（“０”是“本个”），被
　乘数０的后位数３３８超３故进１（“１”是“后进”）；“本个”“０”加
“后进”“１”等于１，所以积的第一位是“１”。
　　积的第二位“０”这样算：３乘以３得９（“９”是“本个”），后位３８
超３故进１（“１”是“后进”），９加１等于１０（满１０只取和的个位数），
所以积的第二位是“０”。
　　积的第三位“１”这样算：３乘以３得９（“本个”），后位８超６故进２
（“后进”），９加２等于１１（取个位“１”），所以是“１”。
　　积的第四位“６”这样算：８乘以３得２４（这里“２４”后面的“４”是
“本个”），后位６７超６故进２（“后进”），４加２等于６，所以是“６”。
　　积的第五位“０”这样算：６乘以３得１８（“１８”后面的“８”是“本
个”），后位７超６进２（“后进”），８加２等于１０（取个位０），所以是
“０”。
　　积的末位“１”这样算：７乘以３得２１，个位是１，后位不进，所以是“
１”。
　　不同的乘数用不同的进位规律进行计算，运算方法同上例乘数为３的方法同
样。运算速度随运算技巧的不断熟练而逐步加快。

题目意思就是是否存在ai,bj，使得l<=cij*(ai/bj)<=u (1<=i<=n,1<=j<=m)成立
首先，把cij除到两边:l'<=ai/bj<=u'，如果差分约束的话，应该是ai-bj的形式，于是可以取对数
log(l')<=log(ai)-log(bj)<=log(u')
 
把log(ai)和log(bj)看成两个点ai和bj，化成求最短路的形式：dis[ai]-dis[bj]<=log(u'),dis[bj]-dis[ai]<=-log(l')
然后判负环就行，深搜和广搜都可以
 
注意的是，如果spfa队列判负环：
(1)不必判断某个点入队次数大于N,只要判断是否大于sqrt(1.0*N)
(2)或者所有点的入队次数大于T*N，即存在负环，一般T取2
N为所有点的个数
 
代码：
spfa队列版本
#include<iostream>
#include<memory.h>
#include<string>
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
using namespace std; 
const int MAX=805;
struct node
{
	int v,next;
	double c;
}g[MAX*MAX];
int adj[MAX];
int n,m,e;
double dis[MAX],l,u;
bool vis[MAX];
int cnt[MAX];
void add(int u,int v,double c)
{
	g[e].v=v; g[e].c=c; g[e].next=adj[u]; adj[u]=e++;
}
bool spfa()
{
	int i,u,v;
	int limit=(int)sqrt(1.0*(n+m));
	//int limit=2*(n+m);
	queue<int>que;
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	for(i=0;i<=n+m;i++)
	{
		dis[i]=0;
		que.push(i);
	}
	while(!que.empty())
	{
		u=que.front();
		que.pop();
		vis[u]=false;
		for(i=adj[u];i!=-1;i=g[i].next)
		{
			v=g[i].v;
			if(dis[v]>dis[u]+g[i].c)
			{
				dis[v]=dis[u]+g[i].c;
				if(!vis[v])
				{
					vis[v]=true;
					if(++cnt[v]>limit)//或者cnt[v]>sqrt(1.0*(n+m)) 
						return false;
					que.push(v);
				}
			}
		}
	}
	return true;
}
int main()
{
	int i,j;
	double t;
	while(scanf("%d%d %lf %lf",&n,&m,&l,&u)!=EOF)
	{
		e=0;
		memset(adj,-1,sizeof(adj));
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				scanf("%lf",&t);
				add(j+n,i,log(u/t));
				add(i,j+n,-log(l/t));
			}
		}
		if(spfa())
			puts("YES");
		else
			puts("NO");
	}
	return 0;
} 
 
spfa深搜版本
#include<iostream>
#include<memory.h>
#include<string>
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
using namespace std; 
const int MAX=805;
struct node
{
	int v,next;
	double c;
}g[MAX*MAX];
int adj[MAX];
int n,m,e;
double dis[MAX],l,u;
bool vis[MAX],inStack[MAX];
inline void add(int u,int v,double c)
{
	g[e].v=v; g[e].c=c; g[e].next=adj[u]; adj[u]=e++;
}
bool spfa(int u)
{
	int i,v;
	if(inStack[u])
		return false;
	inStack[u]=true;
	vis[u]=true;
	for(i=adj[u];i!=-1;i=g[i].next)
	{
		v=g[i].v;
		if(dis[v]>dis[u]+g[i].c)
		{
			dis[v]=dis[u]+g[i].c;
			if(!spfa(v))
			{
				return false;
			}
		}
	}
	inStack[u]=false;
	return true;
}
bool ok()
{
	int i,u,v,cnt=0;
	memset(vis,0,sizeof(vis));
	memset(inStack,0,sizeof(inStack));
	//memset(cnt,0,sizeof(cnt));
	for(i=0;i<=n+m;i++)
	{
		dis[i]=0;
		//que.push(i);
	}
	for(i=1;i<=n+m;i++)
	{
		if(!vis[i])
		{
			if(!spfa(i))
			{
				return false;
			}
		}
	}
	return true;
}
int main()
{
	int i,j;
	double t;
	while(scanf("%d%d %lf %lf",&n,&m,&l,&u)!=EOF)
	{
		e=0;
		memset(adj,-1,sizeof(adj));
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				scanf("%lf",&t);
				add(j+n,i,log(u/t));
				add(i,j+n,-log(l/t));
			}
		}
		if(ok())
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}