跳至内容
OI 博客
数学

数学

必知数学

必知的数学知识（按照毕导的话来说 这都是小学二年级的

模运算

这个非常重要 不少题都需要对结果取余

如果 a≡b(modn) 且 c≡d(modn)，那么a±c≡b±d(modn)ac≡bd(modn) \begin{gathered} \text{如果 } a \equiv b \pmod{n} \text{ 且 } c \equiv d \pmod{n}\text{，那么} \\ a \pm c \equiv b \pm d \pmod{n}\\ ac \equiv bd \pmod{n} \end{gathered}

逆元

如果存在一个数 x，使得b⋅x≡1(modc)那么 x就是b的逆元 记作b−1此时 ab=a⋅x(modn) \begin{gathered} \text{如果存在一个数 }x\text{，使得} b \cdot x \equiv 1 \pmod{c}\\ \text{那么 }x\text{就是}b\text{的逆元 记作}b^{-1} \text{此时 } \frac{a}{b} = a \cdot x \pmod{n} \end{gathered}

奇偶性

取余法
return x % 2;
AND 操作
本质上是对1进行AND操作 return x & 1;

不难发现位运算比取余法要快得多

阶乘

对于一个正整数 nn 都有 n!=n∗(n−1)∗(n−2)∗...∗1n! = n*(n-1)*(n-2)*...*1
对于需要大量使用 不同数的阶乘 时 会产生大量的重复计算 这时 可以建立数组来储存

前 nn 个自然数之和

循环/递归法

这种方法太慢了 但逻辑很简单 时间复杂度 O(n)O(n) 非常慢

int sum(int n){
    int ans = 0;
    for(int i = 1;i<=n;i++){
        ans += i;
    }
    return ans;
}

公式法

不难发现 这是一个等差数列 则有

S=(n+1)n2 S = \frac{(n+1)n}{2}

这个公式中 (n+1)n(n+1)n 数太大了 稍作变形

S=(n+12)n S = (\frac{n+1}{2})n

这样就减少了溢出的风险 若不加 double 的话 记得判断 n 的奇偶性

快速幂

如果 a+b=n 则:xn=xa⋅xb依此原理 可将正整数 n拆分成2a+2b+2c+...+1 \begin{gathered} \text{如果 } a + b = n\text{ 则:}\\ x^{n} = x^{a} \cdot x^{b}\\ \text{依此原理 可将正整数 }n\text{拆分成} 2^a + 2^b + 2^c +...+1 \end{gathered}

故便得此代码

long long qpow(long long a, long long b) {
    long long res = 1;
    for (; b; b >>= 1, a = a * a) // WTF AI写代码这么牛逼?
        if (b & 1) res *= a;
    return res;
}