Skip to main content

第19章 数学问题

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

19.1 数列​

19.1 等差数列​

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

  • 通项：an=a1+(n−1)×da_n = a_1 + (n-1) \times d
  • 前n项和：Sn=n×(a1+an)÷2S_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.2 等比数列​

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

  • 通项：an=a1×qn−1a_n = a_1 \times q^{n-1}
  • 前n项和：q≠1q≠1时 Sn=a1×(1−qn)/(1−q)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遍历到n\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×2×3…×nn! = 1×2×3…×n，规定 0!=10! = 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，int极易溢出；
  3. 最小公倍数 = 两数乘积 / 最大公约数；
  4. 所有公因数一定是最大公因数的约数。