第19章 数学问题

本章讲解竞赛与考试高频数学模型：等差、等比数列，质数合数，阶乘，因数、公约数相关算法。

19.1 数列

19.1.1 等差数列

定义：后项减前项差值固定（公差 d）

• 通项：$a_n = a_1 + (n-1) \times d$
• 前 n 项和：$S_n = n \times (a_1+a_n) \div 2$

示例代码：输出首项 2，公差 3，共 5 项

#include <iostream>
using namespace std;
int main()
{
    int a1 = 2, d = 3, n = 5;
    for (int i = 0; i < n; i++)
    {
        int term = a1 + i * d;
        cout << term << " ";
    }
    return 0;
}

19.1.2 等比数列

定义：后项÷前项比值固定（公比 q，q≠0）

• 通项：$a_n = a_1 \times q^{n-1}$
• 前 n 项和：$q \neq 1$ 时 $S_n = a_1 \times (1-q^n)/(1-q)$

示例代码：首项 2，公比 3，4 项

#include <iostream>
using namespace std;
int main()
{
    int a1 = 2, q = 3, n = 4;
    int t = a1;
    for (int i = 0; i < n; i++)
    {
        cout << t << " ";
        t *= q;
    }
    return 0;
}

19.2 质数与合数

19.2.1 质数（素数）

大于 1，只能被 1 和自身整除。 判断思路：从 2 遍历到 $\sqrt{n}$，存在能整除则不是质数。

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int n = 7;
    bool isPrime = true;
    if (n <= 1) isPrime = false;
    else
    {
        for (int i = 2; i <= sqrt(n); i++)
        {
            if (n % i == 0)
            {
                isPrime = false;
                break;
            }
        }
    }
    cout << boolalpha << isPrime;
    return 0;
}

19.2.2 合数

大于 1 且不是质数；1 既不是质数也不是合数。

19.3 阶乘

定义 $n! = 1 \times 2 \times 3 \dots \times n$，规定 $0! = 1$。 注意：数值增长极快，使用 long long 防止溢出。

#include <iostream>
using namespace std;
int main()
{
    int n = 5;
    long long res = 1;
    for (int i = 1; i <= n; i++)
        res *= i;
    cout << res;
    return 0;
}

19.4 因数

能整除该数的整数；遍历 1~num，取能整除的数。

19.5 公因数与最大公因数（GCD）

19.5.1 辗转相除法（欧几里得算法）

核心：gcd(a, b) = gcd(b, a % b)，余数为 0 时 b 是最大公约数。

#include <iostream>
using namespace std;
int main()
{
    int a = 24, b = 18;
    int t;
    while (b != 0)
    {
        t = a % b;
        a = b;
        b = t;
    }
    cout << a;
    return 0;
}

19.5.2 多个数最大公约数

先求前两个的 GCD，再和下一个数字求 GCD，循环处理。

19.6 补充要点

1. 质数判断循环只需到平方根，大幅提速；
2. 阶乘必须用 long long，int 极易溢出；
3. 最小公倍数 = 两数乘积 / 最大公约数；
4. 所有公因数一定是最大公因数的约数。

练习题（2 级单选风格）

1. 判断一个整数 n 是否为质数时，试除循环只需进行到？
   • A. n
   • B. n/2
   • C. √n（sqrt(n)）
   • D. n-1
2. 用 int 存储 13!（阶乘）会？
   • A. 正常存储
   • B. 数值溢出
   • C. 变成 0
   • D. 编译报错
3. 求两数的最大公约数（GCD）最常用的方法是？
   • A. 累乘
   • B. 辗转相除法（欧几里得算法）
   • C. 逐次相加
   • D. 取平方根
4. 两数的最小公倍数 LCM(a,b) 等于？
   • A. a × b
   • B. a × b ÷ GCD(a,b)
   • C. GCD(a,b)
   • D. max(a,b)
5. 下列代码执行后输出什么？

   int f = 1;
   for (int i = 1; i <= 5; i++) f *= i;
   cout << f;
   

   • A. 120
   • B. 5
   • C. 25
   • D. 15