数学杂谈

不定时更新，基本上是看到啥写点啥（如果我能看懂的话）总之都给我去学数学！！！

也许会比较啰嗦，想学数学的不是很建议看这篇（

对数

对数：如果 $a^{x} = N (a > 0$ 且 $a \neq 1)$ ，那么数 x 叫做以 a 为底 N 的对数（logarithm），记作 $x = \log_{a} N$ 。其中，a叫做对数的底数，N叫做真数。

感觉就是幂运算的逆运算，也就是算出 N 是 a 的几次方。

几个灰常好用的运算公式：

$a^{\log_{a} b} = b$
$\log_{a} (M N) = \log_{a} M + \log_{a} N$
$\log_{a} (\frac{M}{N}) = \log_{a} M - \log_{a} N$
$\log_{a} M^{n} = n \times \log_{a} M$
$\log_{a} \sqrt[n]{M} = \frac{1}{n} \log_{a} M$
$\log_{a} (a^{k}) = k$

还有个叫换底公式的东西，长这个样子： $\log_{a} b = \frac{\log_{c} b}{\log_{c} a}$ ，用处嘛就是字面意思，把两个同底不同真数的对数凑成一个对数

对于以上公式，可以尝试着自己推一下，具体的想不出来可以抽象一点，就比如想这个真数里面有几个对数相乘，然后可以按照乘法的一些性质证一证。（网上一搜一大把，咱也没啥独特见解就不证了，免得带歪） Ricky的证明

放道题：给定一个 n，求 $2^{n}$ 的首位数字， $n \leq 10^{12}$ 。

这里先把求首位数字的柿子列出来，设 $2^{n}$ 长度为 $m$ ，则首位数字 $a = ⌊ \frac{2^{n}}{10^{m}} ⌋$ 看起来不是很可做，考虑怎么把 m 求出来，既然要求一个数 $x$ 是 $y$ 的几次方，不难想到运用对数，这样就可以表示为 $m = ⌊ \log_{10} 2^{n} ⌋$ ， $2^{n}$ 肯定是算不出来的嘛，太大了实在是，那就运用对数的运算规律： $\log_{a} b^{n} = n \times \log_{a} b$ ，就可以化成 $m = ⌊ n \times \log_{10} 2 ⌋$ 因为 m 为整数所以记得向下取整。但是之前的那个分式里分子还是 $2^{n}$ 怎么办呢？都算出来 $\log_{10} 2^{n}$ 了咱直接再套到 10 上不就得了。根据对数的性质我们可以知道 $a^{l o g_{a} n} = n$ 那不就 $10^{n \times \log_{10} 2} = 2^{n}$ 嘛，这里不需要向下取整了因为我们要相等，那最终这个分式柿子就被转化成了 $a = ⌊ \frac{10^{n \times \log_{10} 2}}{10^{⌊ n \times \log_{10} 2 ⌋}} ⌋$ ，我们就可以愉快的敲代码了！

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const long double t=log10(2);
int m;
long double a;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>m;
    while(m--){
        cin>>a;
        long long tmp=a*t;
        printf("%d\n",(int)pow(10,a*t-tmp));
    }
    return 0;
}

线性基

首先，线性基是个什么东西？在OI中，线性基经常被用来处理与异或相关的问题。具体的，对于一个值域在 $[1, N]$ 的集合 $S$ ，线性基可以通过一个长度为 $\log_{2} N$ 的数组维护这个集合，设一个线性基数组为 $P$ ，则 $P_{i}$ 表示这个值域（一般来说为题目给出的数组）中第一个在二进制下最高位的 $1$ 在第 $i$ 位的数。

那它能做些啥呢？上面提到它可以维护一个值域，具体来说就是这个值域中的所有数都可以通过线性基里的数异或得到，这样，我们在查询异或和时可以极大地缩小次数。

插入

插入一个数 $x$ 它的二进制最高位为 $i$

考虑两种情况：

线性基的第 $i$ 位为 0，此时直接插入即可
线性基的第 $i$ 位有值了，这时要将 $x = x \oplus P_{i}$ ，然后反复寻找一直到 $x$ 可以插入或 $x = 0$ 为止，这样是为了将 $x$ 的每一个为 1 的二进制位都确保插入到线性基中，从而保证上文提到的线性基维护值域的性质