9.1 KiB
对数知识推导及应用
一、对数知识
1、对数概念
如果\large N=a^x,那么数x称为以a为底N的对数。记做：
\large x=log_aN其中，a称做底数，N称做真数。需要注意的是底数a的限制条件：a>0,a \neq 1。
2、对数与指数关系
对数与指数互为逆运算：
- 指数运算: 求
10的2次方，即：\large 10^2=100 - 对数运算：求
10的多少次方等于100，即：\large log_{10}100=2
3、对数形式
-
常用对数：以
10为底的对数记做：\large log_{10}N=lgN -
自然对数：以无理数
e=2.71828...为底数的对数简记为：lnN自然底数e的含义 -
一般对数：
log_aN
4、对数性质
1的对数
1的对数是0:
\large log_a1=0$$
积的对数
\large log_aMN=log_aM+log_aN$$
证明：设\large log_aM=p,log_aN=q
则\large a^p=M,a^q=N,代入\large log_aMN,
得\large log_aMN=log_a({a^p\cdot a^q})=log_a{a^{p+q}}=p+q=log_aM+log_aN
证毕
商的对数
\large log_a{\frac{M}{N}}=log_aM-log_aN$$
证明：设\large log_aM=p,log_aN=q
则\large a^p=M,a^q=N,代入\large \displaystyle log_a{\frac{M}{N}},
得\large \displaystyle log_a{\frac{M}{N}}=log_a{(\frac{a^p}{a^q})}=log_a{a^{p-q}}=p-q=log_aM-log_aN
证毕
幂的对数
\large log_aM^b=b\cdot log_aM$$
证明：设\large log_aM=p,则\large a^p=M
则\large a^p=M,代入 \large log_aM^b
得\large log_aM^b=log_a{(a^p)^b}=log_a{a^{p\cdot b}}=pb=b\cdot log_aM$$
证毕
对数恒等式
\large a^{log_aM}=M$$
证明： 设\large \displaystyle log_aM=p,则\large \displaystyle a^p=M,代入\large \displaystyle a^{log_aM}
得\large \displaystyle a^{log_aM}=a^{log_aa^p}=a^p=M
证毕
5、换底公式
\large log_bN=\frac{log_aN}{log_ab}
证明：
设\large log_bN=x,则\large b^x=N
两边同时取以a为底的对数
\large log_ab^x=log_aN \\
x\cdot log_ab=log_aN \\
x=\frac{log_aN}{log_ab} \\
即log_bN=\frac{log_aN}{log_ab}
6、其他公式
\large log_{a^n}a=\frac{1}{n}
证明：
设\large log_{a^n}a=p
则\large (a^n)^p=a,即\large a^{np}=a
两边同时取以10为底对数，\large lga^{np}=lga \
\Rightarrow np \cdot lga=lga \
\Rightarrow
np=1 \
\Rightarrow p=\frac{1}{n}
**证毕**
---
<font color='red' size=4><b>$$\large \frac{1}{log_ab}=log_ba $$</b></font>
证明：
用换底公式：
$$\large \frac{1}{log_ab}=\frac{1}{\frac{lgb}{lba}}=\frac{lga}{lgb}=log_ba$$
**证毕**
---
<font color='red' size=4><b>$$\large log_{a^n}M=\frac{1}{n}\cdot log_aM $$</b></font>
证明：设$\large log_aM=p$
则$\large a^p=M$,代入$\large log_{a^n}M$
$$\large log_{a^n}a^p=p\cdot log_{a^n}a=\frac{1}{n}\cdot p=\frac{1}{n}\cdot log_aM$$
**证毕**
---
### 二、典型应用
#### 1、求数$a$的位数
~~暴力解法~~
```c++
#include <stdio.h>
int a,b;
int main(){
scanf("%d",&a);
while(a){
a=a/10;
b++;
}
printf("%d ",b);
return 0;
}
```
可以吗？可以，就是如果算的数太多，而且每个数很大，就太慢了，人总是贪婪的，想要更快的办法：
<font color='blue' size=4><b>公式</b></font>
<font color='red' size=4><b>
$$\large a的位数 = log_{10}(a) + 1$$
</b></font>
证明:
假设 $10^{x-1} <= a < 10^{x}$,(想一想 $100$,$999$和$1000$) ，可见$a$的位数为 $x$ 位。
我们再对上式用 $log_{10}$
$$\large log_{10}10^{x-1}<=log_{10}a<log_{10}10^x$$
得 $$\large x-1 <= log_{10}a < x$$
则 $$\large x-1 = log_{10}a \\
\Rightarrow \\
x = log_{10}a + 1$$
所以：$a$的位数为 $$\large log_{10}a + 1$$
**证毕**
$C++$语言中只有$log$(以$e$为底)和$log10$(以$10$为底)两种函数。
如果想表达$log_ab$ 那么可以使用换底公式：$log(b)/log(a)$来解决。
```c++
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int n;
cin>>n;
cout<<(int)(log10(n))+1;
return 0;
}
```
---
#### 2、求数$n!$的位数
**1、递推法**
先利用一下求数字$a$的位数公式：
$$\large n!的位数=log_{10}(n!)+1$$
展开一下阶乘的概念
$$\large =log_{10}(n\times(n-1)\times(n-2)\times...\times1)+1$$
利用积的对数性质
$$\large =log_{10}(n)+log_{10}(n-1)+…+log_{10}(1)+1$$
编程时，利用这个递推的关系**由小到大**进行递推即可。
#### 练习题
[$POJ$ $1423$](http://poj.org/problem?id=1423)
```c++
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
/*
思想：底数相同的两个数相乘底数不变，指数相加。
通过log10(x)得到指数，依次相加即可，即可以得到阶乘的位数
*/
const int N = 10000010;
int a[N];
int main() {
//预处理出阶乘的位数
double x = 0;
for (int i = 1; i < N; i++) {
x += log10((double)i); // POJ对于log10(i)会报编译错误，需要转为double
a[i] = x + 1;
}
// T次询问
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
printf("%d\n", a[n]);
}
return 0;
}
```
这样的做法时间复杂度为 $O(n)$ ，当$n$的范围特别大时就不好用了，下面我们来找到$O(1)$的做法 <font color='red' size=5><b>斯特林公式</b></font> :
**2、斯特林($Stirling$)公式**
斯特林公式 ： 是一条用来 <font color='blue' size=5><b>计算$n$的阶乘近似值</b></font> 的数学公式。一般来说，当$n$很大的时候，$n$阶乘的计算量十分大，所以斯特林公式十分好用，即使在$n$很小的时候，斯特林公式的取值也十分准确。
$$\LARGE n!=\sqrt{2\pi n}(\frac{n}{e})^n$$
* 用斯特林公式求$n!$
* 再用求$a$的位数公式计算$n!$的位数：$$\displaystyle \LARGE log_{10}( \sqrt{2\pi n} *(\frac{n}{e})^n)+1$$
变形一下：
<font color='red' size=4><b>
$$\LARGE log_{10}(2\pi n)/2+nlog_{10}(n/e)+1$$</b>
</font>
#### 练习题
[$POJ$ $1423$](http://poj.org/problem?id=1423)
```c++
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <math.h>
#include <cstdio>
#define PI acos(-1)
#define E exp(1.0)
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
int y = log10(2 * PI * n) / 2 + log10(n / E) * n + 1;
printf("%d\n", y);
}
}
```
* 主要是利用利用数学函数中的反三角函数，但是要注意一定引入$math$包$$\LARGE acos(-1)=\pi$$
#### 3、求$2^p-1$的位数
首先我们知道$\large 2^p-1$与$\large 2^p$有着相同的位数，因为$2$的次方满足了<font color='blue' size=4><b>最后一位不为零</b></font>的要求，所以<font color='red' size=4><b>减一后位数并不会改变</b></font>，那么我们可以直接求$\large 2^p$的位数。
<font color='blue' size=4><b>使用的知识是：求数字$a$的位数办法：</b></font>
<font color='red' size=4><b>$$\LARGE 2^p位数=log_{10}2^p+1= p\cdot log_{10}{2}+1$$</b></font>。
练习题：
[P1045 [NOIP2003 普及组] 麦森数](https://www.luogu.com.cn/problem/P1045)
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], al;
int b[N], bl;
void mul(int a[], int &al, int b[], int bl) {
int c[N] = {0}, cl = al + bl;
for (int i = 1; i <= al; i++)
for (int j = 1; j <= bl; j++)
c[i + j - 1] += a[i] * b[j];
int t = 0;
for (int i = 1; i <= al + bl; i++) {
t += c[i];
c[i] = t % 10;
t /= 10;
}
memcpy(a, c, sizeof c);
al = min(500, cl);
//前导0
while (al > 1 && a[al] == 0) al--;
}
//快速幂+高精度 x^k
void qmi(int x, int k) {
a[++al] = 1, b[++bl] = x; // 2 ^100 b[1]=2
while (k) {
if (k & 1) mul(a, al, b, bl);
k >>= 1;
mul(b, bl, b, bl);
}
}
int main() {
//计算 2^p-1的值
int y;
cin >> p;
//利用快速幂，计算2^p
qmi(2, p);
//最后一位减去一个1，因为2^k最后一位肯定不是0，所以减1不会产生借位，直接减去即可！
a[1]--;
//一共多少位
printf("%d\n", (int)(p * log10(2) + 1));
for (int i = 500; i; i--) {
printf("%d", a[i]);
//该换行了,就是到了第二行的行首
if ((i - 1) % 50 == 0) puts("");
}
return 0;
}
```