python/TangDou/AcWing/Log/对数知识推导及应用.md

## 对数知识推导及应用

### 一、对数知识

#### 1、对数概念
如果$\large N=a^x$,那么数$x$称为以$a$为底$N$的对数。记做：
$$\large x=log_aN$$

其中，$a$称做底数，$N$称做真数。需要注意的是底数$a$的限制条件：$a>0,a \neq 1$。

#### 2、对数与指数关系
<font color='blue' size=4><b>对数与指数互为逆运算：</b></font>
* 指数运算: 求$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$的含义](https://www.toutiao.com/article/6986077169411703310)

* 一般对数：$log_aN$

#### 4、对数性质

<font color='blue' size=4><b>$1$的对数</b></font>
$1$的对数是$0$:
<font color='red' size=4><b>$$\large log_a1=0$$</b></font>

<font color='blue' size=4><b>积的对数</b></font>
<font color='red' size=4><b>$$\large log_aMN=log_aM+log_aN$$</b></font> 

证明：设$\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$　

**证毕**

---
<font color='blue' size=4><b>商的对数</b></font>
<font color='red' size=4><b>$$\large log_a{\frac{M}{N}}=log_aM-log_aN$$</b></font>
证明：设$\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$

**证毕**

---
<font color='blue' size=4><b>幂的对数</b></font>
<font color='red' size=4><b>$$\large log_aM^b=b\cdot log_aM$$</b></font>
证明：设$\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$$

**证毕**

--- 
<font color='blue' size=4><b>对数恒等式</b></font>
<font color='red' size=4><b>$$\large a^{log_aM}=M$$</b></font>
证明：　设$\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、换底公式
<font color='red' size=4><b>
$$\large log_bN=\frac{log_aN}{log_ab}$$
</b></font>

证明：
设$\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、其他公式
<font color='red' size=4><b>$$\large log_{a^n}a=\frac{1}{n}$$</b></font>
证明：
设$\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;
}
```