简单数学

加法

A + B 像加法一样

vector<int> add(vector<int> &A, vector<int> &B){
    int tmp = 0;
    if (A.size() < B.size()) return add(B, A);
    vector<int> C;

    for (int i = 0; i < A.size(); i ++){
        tmp += A[i];
        if (i < B.size()) tmp += B[i];
        C.push_back(tmp % 10);
        tmp /= 10;
    }

    while (tmp) C.push_back(tmp % 10), tmp /= 10;
    while (res.back() == 0 && res.size() > 1) res.pop_back();

    return C;

}

乘法

A x b

大数乘小数，将大数各个位数与小数相乘，保存个位，剩余位数待下次运算加上。

#include <iostream>
#include <vector>

using namespace std;

string a;
vector<int> A;
int b;

vector<int> mul(vector<int> &A, int b){
    vector<int> C;

    int tmp = 0;
    for (int i = 0 ; i < A.size() ; i ++){
        tmp += A[i] * b;
        C.push_back(tmp % 10);
        tmp /= 10;
    }

    while (tmp){
        C.push_back(tmp % 10);
        tmp /= 10;
    }

    while (C.size() > 1 && C.back() == 0 ) C.pop_back();

    return C;
}

int main(){
    cin >> a >> b;

    for (int i = a.size() - 1; i >= 0 ; i --) A.push_back(a[i] - '0');

    auto res = mul(A, b);

    for (int i = res.size() - 1 ; i >= 0 ; i --) cout << res[i];

    return 0;
}

A x B

大数乘大数，将各位数乘积结果按位加入结果数组中，此时各位的结果就是各数组元素加入上进位数取个位，即模拟人工笔算

#include <iostream>
#include <vector>

using namespace std;

string a, b;
vector<int> A, B;

vector<int> mul(vector<int> &A, vector<int> &B){
    vector<int> C(A.size() + B.size() + 10, 0);

    for (int i = 0 ; i < A.size() ; i ++)
        for (int j = 0 ; j < B.size() ; j ++)
            C[i + j] += A[i] * B[j];

    int tmp = 0;

    for (int i = 0 ; i < C.size() ; i ++){
        tmp += C[i];
        C[i] = tmp % 10;
        tmp /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

int main() {
    cin >> a >> b;
    for (int i = n.size() - 1; i >= 0 ; i --) A.push_back(a[i] - '0');
    for (int i = m.size() - 1; i >= 0 ; i --) B.push_back(b[i] - '0');

    auto res = mul(A, B);

    for (int i = res.size() - 1; i >= 0 ; i --) cout << res[i];

    return 0;
}

除法

A / b

和手算除法的步骤是一样的，记得去除首 0，翻转答案数组，因为答案是从高位存的

#include <bits/stdc++.h>

using namespace std;

string A;
vector<int> a, ans;

int b;

int divi(vector<int> &ans, vector<int> &A, int b)
{
    int t = 0;
    for (int i = A.size() - 1; i >= 0  ; i --)
    {
        t = t * 10 + A[i];
        ans.push_back(t / b);
        t %= b;
    }

    reverse(ans.begin(), ans.end());

    while (ans.size() > 1 && ans.back() == 0) ans.pop_back();

    return t;
}

int main()
{
    cin >> A >> b;

    for (int i = A.size() - 1; i >= 0 ; i --) a.push_back(A[i] - '0');

    int t = divi(ans, a, b);

    for (int i = ans.size() - 1; i >= 0 ; i --) cout << ans[i];

    puts("");

    cout << t << endl;

    return 0;
}

幂

快速幂

和手写幂运算一样，只要不断地把底数进行平方运算，只需要算 logk 次就可以了。

复杂度：

时间： $O(logn)$

#include <iostream>

using namespace std;
typedef long long LL;

LL qmi(int a, int k, int mod)
{
    LL res = 1;
    while (k)
    {
        if (k & 1) res = res * a % mod;
        a = 1LL * a * a % mod;
        k >>= 1;
    }
    return res;
}
int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        int a, b;
        cin >> a >> b;
        LL res = qmi(a, b); cout << res << endl;
    }
    return 0;
}

阶乘

求阶乘中质因数的指数： $cnt_pmi(a!)= \left\lfloor\frac{a}{p}\right\rfloor + \left\lfloor\frac{a}{p^2}\right\rfloor + ... + \left\lfloor\frac{a}{p^k}\right\rfloor$
证明：

知识点：
1 到 n 中 p 的倍数的个数为[n / p]，[]为向下取整
知识点举例证明：6 / 2 = 3，说明 6 等于 3 个 2 相加
6 = 2 + 2 + 2
5 = 2 + 2 + 1
4 = 2 + 2
3 = 2 + 1
2 = 2
1 = 1
可以看出当加项全为 2 时，总和才能被 2 整除，因此加项的个数就是 1 到 8 中 2 的倍数个数

由分解质因数部分可知，任何一个合数N都可以写成 $N = p_1^{k_1} \* p_2^{k_2} \* ... \* p_n^{k_n}$ ，即若干个质数的若干次幂的积

由 1 到 n 中 p 的倍数的个数为[n / p] 可知， $[\frac{a}{p}]$ 算出了 1 到 a 中 p 的倍数个数，同时也是 a * (a - 1) * ... * 1 中各项为 p 倍数的因数对p^k 中k 的贡献（因为这些倍数都乘起来了，因此至少每个倍数贡献 1），记为 $k_1$ 。而 a!的因数中可能还存在有多贡献的倍数那么 $[\frac{\frac{a}{p}}{p}] = [\frac{a}{p^2}]$ 可表示再次贡献 1 的倍数个数，记为 $k_2$ ，同理可得到 $k = k_1 + k_2 + ... + k_n$ ，由此可证：

阶乘中质因数的指数： $cnt_pmi(a!)= \left\lfloor\frac{a}{p}\right\rfloor + \left\lfloor\frac{a}{p^2}\right\rfloor + ... + \left\lfloor\frac{a}{p^k}\right\rfloor = k$

题目：求 n!中有多少个尾数 0（由于 2 * 5 = 10 , 而 2 的数量比 5 的多，因此 0 的个数取决于 5 的指数）

#include <iostream>

using namespace std;

int n, res;

int main()
{
    cin >> n;

    while (n)
    {
        n /= 5;
        res += n;
    }

    cout << res << endl;

    return 0;
}

对数

对数推导算法的时间复杂度很重要，以下是常用的对数公式

名称	公式
和差	$log_aMN = log_aM + log_aN$
换底	$log_ax=\frac{log_cx}{log_ca}$
次方	$log_{a^n}x^m = \frac{m}{n}log_ax$
互换	$M^{log_aN} = N^{log_aM}$
倒数	$log_ab = \frac{lnb}{lna} =\frac{1}{\frac{lna}{lnb}}= \frac{1}{log_ba}$
链式	$log_cb log_ba = \frac{lnb}{lnc} \frac{lna}{lnb} = log_ca$
还原	$a^{log_ax} = x = log_aa^x$

关于计算机中，很多问题 log 的底数时而为 2，时而为 e，可以用换底公式求出他们的比值： $\frac{log_eN}{log_2N} = \frac{log_kN}{logke} / \frac{log_kN}{log_k2} =log_e2$

日期

闰年判断
1. 非整百年份（不可被 100 整除），可以被 4 整除
2. 整百年份（可被 100 整除）可以被 400 整除
闰年性质
1. 2 月份有 29 天，全年有 366 天
1000ms = 1s

求开方

牛顿迭代法

不讲数值分析，只讲有趣的理解

转载链接open in new window

将"长方形变得更像正方形"的思路也可以得到求 $\sqrt{A}$ 的迭代公式

首先是考虑 $\sqrt{A}$ 是面积为 A 的正方形的边长，如果画一个邻边不等的面积是 A 长方形

设这个长方形的长为 L ，宽为 $A/L$ ，那么怎样能让这个长方形变得更像一个正方形呢？

是要把长变得短一点，宽变得长一点，可以用长和宽的平均数 $(L + A / L) / 2$ 来作为新的长 $L_{new}$

在面积不变的条件下，新的宽是 $A/L_{new}$ 。这样不断操作下去，长方形的长和宽会越来越接近，就一直趋近于 $\sqrt{A}$ 了。

$L_{new}=\frac{1}{2}( L+\frac{A}{L} )$

二分

这节不会详细介绍二分的内容，总而言之，在l 到 r 的范围，寻找满足mid * mid <= x 的条件就行

Fast inverse square root

这个方法非常有趣，原理没搞懂，感兴趣请看 Fast_inverse_square_rootopen in new window

此算法最早可能是于 90 年代前期由 SGI 所发明，后来则于 1999 年在《雷神之锤 III 竞技场》的源代码中应用，但直到 2002－2003 年间才在 Usenet 一类的公共论坛上出现。

此算法首先接收一个 32 位带符浮点数，然后将之作为一个 32 位整数看待

以将其向右进行一次逻辑移位的方式将之取半

并用在浮点数规格代表 $\sqrt{2^{127}}$ 近似值的十六进制“魔术数字”0x5f3759df 减之，如此即可得对输入的浮点数的平方根倒数的首次近似值；

如果想进一步靠近，就继续使用牛顿牛顿迭代

float Q_rsqrt( float number )
{
	long i;
	float x2, y;
	const float threehalfs = 1.5F;

	x2 = number * 0.5F;
	y  = number;
	i  = * ( long * ) &y;                       // evil floating point bit level hacking
	i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
	y  = * ( float * ) &i;
	y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

	return y;
}

go 语言实现

func InvSqrt(x float32) float32 {
    halfx := x * 0.5
    threeSeconds := float32(1.5)

    i := *(*int)(unsafe.Pointer(&x))
    i = 0x5f3759df - (i >> 1) //az

    y := *(*float32)(unsafe.Pointer(&i))
    y = y * (threeSeconds - (halfx * y * y)) // 牛顿迭代
    y = y * (threeSeconds - (halfx * y * y))

    return y
}

# 简单数学

# 加法

# 乘法

# 除法

# 幂

# 快速幂

# 阶乘

# 对数

# 日期

# 求开方

# 牛顿迭代法

# 二分

# Fast inverse square root

简单数学

加法

乘法

除法

幂

快速幂

阶乘

对数

日期

求开方

牛顿迭代法

二分

Fast inverse square root