lapt BlogPostsTagsGallerydemogameLeetCode
力扣算法：数学技巧
|leetcode

数学技巧

质因数分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void zhishu(int x) {
    // 从2开始尝试
    int i = 2;
    // 尝试到 i <= sqrt(x)
    while (i * i <= x) {
        // 如果能整除，就不断除这个质数
        while (x % i == 0) {
            // 这里的i一定是个质数
            // 比如不可能有整除 i=4 的情况，因为会在 i=2 的时候除两次
            cout << i << ",";
            x = x / i;
        }
        i++;
    }
    // 如果x大于1，说明x还是一个质数
    if (x > 1) cout << x << ",";
}

快速幂

快速幂思想及实现

快速幂思想其实很简单，就是公式的转换

  1. 当指数是偶数时，我们可以让指数除以2，底数乘以底数
  2. 当指数是奇数时，我们可以将指数变为偶数

例如 2^10

210→45→4×44→4×162→4×2561→4×2562^{10}\rightarrow 4^{5}\rightarrow 4\times4^4\rightarrow 4\times16^2\rightarrow 4\times256^1\rightarrow 4\times256 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 求 a^n 次
long long quickpow(long long a, long long n, long long mod) {
    // mod = 1e9+7
    long long ans = 1;
    while (n) {
        // 奇数
        if (n & 1) {
            ans = ans * a % mod;
        }
        // 偶数
        n = n >> 1;
        a = a * a % mod;
    }
    return ans;
}

注意这类题中常常会涉及溢出的问题，要注意一切加和乘号，确保中间变量类型都是long long

mod = 10^9 + 7

写成 mod =1e9+7 而不是 10e9+7

位运算

异或统计出现的次数

相关题目 1 2

1
sum = sum ^ (1 << n)

如果出现次数为偶数，那么异或结果就是0，如果出现次数为奇数，异或结果就是1。最后统计位数上1的个数，就知道那一位上出现次数是奇数了。

统计1的个数

1
2
3
4
5
int n_1 = 0;
while (a) {
    if ((a & 1) == 1) n_1++;
    a = a >> 1;
}

数列

等差/等比数列

质数

找一个小于n的所有质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
std::vector<int> findPrimes(int n) {
    std::vector<bool> isPrime(n+1, true);
    std::vector<int> primes;
    for (int p = 2; p * p <= n; ++p) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    for (int p = 2; p <= n; ++p) {
        if (isPrime[p]) {
            primes.push_back(p);
        }
    }
    return primes;
}
leetcode