数学相关算法

1. 根据数据范围猜算法

算法数据范围初定：单数据 10 的 9 次方以内无脑用 int，单数据 10 的 18 次方以内无脑 long long，更高的数据量需要考虑 long double（10 的 308 次方左右），但是注意：long double 虽然能表示很大的数，但精度不够稳定，误差较大！对准确性要求极高的场景下，就不太靠谱了。这时就需要考虑高精度算法和计算库了。还有在多数据涉及加法和乘法操作时，注意边界溢出！

1. 不同数据规模下可接受的算法时间复杂度

2. 常见算法及其典型时间复杂度

只列举一下常用的，等学到那些比较难的算法的时候，这个文档的内容都应该已经印到脑子里了～

提示：算法竞赛或面试中，先看数据范围 $n$，再反推允许的时间复杂度，能快速排除不可行方案，聚焦正确解法。

2. 基本数学函数（<cmath>）

3. 数值算法（<algorithm> & <numeric>）

1
2
3
4
5
6
7
8
9
10

// 对于最大公约数和最小公倍数，如果环境不支持，可以手动实现其两者功能：
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b)
{
    return (a * b) / gcd(a, b);
}

C++17 及以上建议使用标准库的 gcd() 和 lcm() 函数。

4. 常见相关常量（也在 <climits> 中）

注意事项：

• 不要混淆 <climits>（C++） 和 <limits.h>（C）。
• 如果你用的是 C++，推荐使用 <climits>。
• INT_MAX 是编译器根据系统架构定义的，保证可移植性。

定义 π 常量：

1. 传统数学函数计算法（C++11 及以上都支持）：

   • acos(-1.0) 计算的是余弦值为 - 1.0 的角度，这个角度正好是 π 弧度（180 度），这种方式不依赖于任何特定的库或编译器扩展。
   • 优点：兼容性好，不依赖特定编译器或标准库版本。
   • 缺点：需要包含 <cmath> 头文件。

   1 2 3 4 5 6 7 8 9

   #include <cmath> // 最常用的方式 const double PI = acos(-1.0); // 其他等效方式 const double PI = atan(1.0) * 4; const double PI = asin(1.0) * 2; const double PI = M_PI; // 注意：这不是标准 C++，但很多编译器支持

2. 直接数值定义法：

   • 优点： 不需要任何头文件，计算最快。
   • 缺点： 精度有限，需要手动输入足够多的小数位。

   1 2 3 4 5 6 7 8

   // 单精度 const float PI = 3.14159265358979323846f; // 双精度 const double PI = 3.14159265358979323846; // 长双精度 const long double PI = 3.14159265358979323846264338327950288L;

3. C++11 constexpr 方式：

   • 优点： 编译期计算，不占用运行时资源。
   • 缺点： 需要 C++11 及以上标准，且 acos 在 constexpr 中的支持因编译器而异。

   1 2	#include <cmath> constexpr double PI = acos(-1.0);

4. C++20 标准库方法（推荐）：

   • 优点： 标准、精确、类型安全。
   • 缺点： 需要 C++20 及以上标准。

   1 2 3 4 5 6 7 8 9

   #include <numbers> // 使用 double 精度 const double PI = std::numbers::pi; // 指定精度 const float PI_f = std::numbers::pi_v<float>; const double PI_d = std::numbers::pi_v<double>; const long double PI_ld = std::numbers::pi_v<long double>;

5. 随机数（<cstdlib>）

随机数是竞赛中的骗分小技巧，正确使用会有意想不到的效果，只能作为最后挣扎的手段。 当然，随机数存在随机化搜索、随机贪心算法、蒙特卡洛方法、随机化哈希等一系列高级用法，但是涉及到这些的题目基本就不是普通人能做的了，咱就图一乐，会 控制 随机数骗一点分已是很了不起了！

1
2
3
4
5
6
7
8
9
10
11

#include <cstdlib>
#include <ctime>

// 初始化随机种子
srand(time(0));

// 生成随机数
int rand_num = rand();                  // [0, RAND_MAX]
int rand_0_99 = rand() % 100;           // [0, 99]
int rand_1_100 = rand() % 100 + 1;      // [1, 100]
int rand_a_b = rand() % (b - a + 1) + a; // [a, b]

6. 位运算（GCC 内置）

说实话位运算用得不多，但用的好效率很高，人也是真厉害！注意：竞赛中常用 GCC 编译器，可使用 __builtin 系列函数优化位运算操作。

1. 基础位运算操作

2. 位运算函数

3. 常用位运算技巧

1. 判断是否为 2 的幂次

1
2
3
4

bool isPowerOfTwo(int n)
{
    return n > 0 && (n & (n - 1)) == 0;
}

2. 判断奇偶性

1
2
3
4
5
6
7
8
9

bool isEven(int x)
{
    return (x & 1) == 0;  // 偶数
}

bool isOdd(int x)
{
    return (x & 1) == 1;   // 奇数
}

3. 统计二进制中 1 的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int countSetBits(int n)
{
    int count = 0;
    while (n)
    {
        count++;
        n &= n - 1;  // 清除最低位的 1
    }
    return count;
}

// 或者使用 GCC 内置函数
int countSetBits(int n)
{
    return __builtin_popcount(n);
}

4. 计算二进制中 0 的个数

1
2
3
4

int countZeroBits(int n, int bits = 32)
{
    return bits - __builtin_popcount(n);
}

5. 清除最低位的 1

1
2
3
4

int clearLowestBit(int n)
{
    return n & (n - 1);
}

6. 获取最低位的 1

1
2
3
4

int getLowestBit(int n)
{
    return n & -n;
}

7. 三角函数（<cmath>）