• C++
  • 数论四大基础 C++ 教程(GESP五级适用)

  • @ 2026-10-21 22:35:14

数论四大基础 C++ 教程(GESP五级适用)

包含:带余除法、算术基本定理、欧几里得算法、同余与剩余类

面向GESP5级,全部带可直接运行代码、逐行注释、例题、课堂小结,适合上课讲

前置说明

数据范围:GESP一般到 101210^{12},统一使用 long long; 头文件统一:

#include <iostream>
using namespace std;
typedef long long ll;

一、带余除法(除法算式:a=b×q+ra = b \times q + r)

✅ 数学定义(带余除法)

对任意整数 aa、正整数 bb,存在唯一一对整数 (q,r)(q,r),满足:

a=b⋅q+r,0≤r<ba = b\cdot q + r,\quad 0\le r < b
  • aa:被除数
  • bb:除数
  • qq:商
  • rr:余数

重点:余数一定 ≥0,并且严格小于除数! 例:17=5×3+217 = 5\times 3 + 2,商3,余数2; −17=5×(−4)+3-17 = 5\times(-4)+3,余数不能是负数。

✅ C++ 注意坑

C++ 中 % 取模,负数的取模结果符号和被除数一致,和数论里带余除法要求的 r≥0r\ge0 不一样! 👉 需要写函数修正,得到标准非负余数。

✅ 代码:求标准带余除法的商、余数

#include <iostream>
using namespace std;
typedef long long ll;

// 带余除法:a ÷ b,b>0,返回合法余数r(0<=r<b)
ll mod(ll a, ll b)
{
    ll r = a % b;
    if(r < 0) r += b; // 负数修正,保证余数>=0
    return r;
}

int main()
{
    ll \(a,b\);
    cin >> a >> b;
    ll q = a / b;
    ll r = mod(\(a,b\));
    // 数学式子:a = b * q + r
    cout << a << " = " << b << " * " << q << " + " << r << endl;
    cout << "商 q = " << q << ",余数 r = " << r << endl;
    return 0;
}

✅ 课堂例题

输入:17 5 输出:17 = 5 * 3 + 2 输入:-17 5 输出:-17 = 5 * -3 + 3

✅ 小结

  1. 带余除法是所有数论的地基,gcd、同余都建立在它上面;
  2. C++原生%不能直接当数论余数,负数必须修正。

二、算术基本定理(唯一分解定理)

✅ 数学定义

任何大于1的正整数 nn,都可以唯一分解成素数乘积(不计顺序):

n=p1e1⋅p2e2…pkekn = p_1^{e_1}\cdot p_2^{e_2}\dots p_k^{e_k}

p1,p2…pkp_1,p_2\dots p_k 是互不相同质数,ei≥1e_i\ge1 为指数。

就是我们奇妙数字一题用到的定理!

✅ 算法思路:试除法分解质因数

  1. ii 从2枚举到 n\sqrt{n};
  2. 如果 ii 能整除 nn,统计指数,不断把n除以i;
  3. 循环结束,如果剩下的n>1,说明剩下本身是质数。

✅ C++完整代码,输出分解式

#include <iostream>
using namespace std;
typedef long long ll;

// 算术基本定理:试除法质因数分解
void factor(ll n)
{
    cout << n << " = ";
    bool first = true;
    for(ll i = 2; i*i <= n; i++)
    {
        if(n % i == 0)
        {
            int cnt = 0;
            while(n % i == 0)
            {
                cnt++;
                n /= i;
            }
            if(!first) cout << " * ";
            first = false;
            cout << i << "^" << cnt;
        }
    }
    if(n > 1)
    {
        if(!first) cout << " * ";
        cout << n << "^1";
    }
    cout << endl;
}

int main()
{
    ll x;
    cin >> x;
    factor(x);
    return 0;
}

✅ 测试样例

输入 1000 → 输出 1000 = 2^3 * 5^3 输入 128 → 输出 128 = 2^7

✅ 小结

  1. 分解结果唯一;
  2. GESP高频考点:奇妙数字、B-smooth数、有限小数判断全部依赖它;
  3. 适合 101210^{12} 以内,i*i 要开long long,防止溢出。

三、欧几里得算法(辗转相除法,求gcd最大公因数)

✅ 数学依据(带余除法推导)

gcd⁡((a,b))=gcd⁡(b, a mod b)\gcd((a,b))=\gcd(b,\ a\bmod b)

一直递归,直到余数为0,此时b就是最大公因数。

推论:\(\gcd(a,0)=a)

✅ 递归版 + 迭代版两份代码

版本1:递归写法(简洁,适合教学)

#include <iostream>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b)
{
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

int main()
{
    ll x,y;
    cin >> x >> y;
    cout << "gcd(" << x << "," << y << ") = " << gcd(x,y) << endl;
    return 0;
}

版本2:迭代写法(推荐上机,无栈溢出风险)

#include <iostream>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b)
{
    while(b != 0)
    {
        ll r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main()
{
    ll x,y;
    cin >> x >> y;
    cout << gcd(x,y) << endl;
    return 0;
}

✅ 拓展:最小公倍数 lcm

lcm((a,b))=a⋅bgcd⁡((a,b))\text{lcm}((a,b)) = \dfrac{a\cdot b}{\gcd((a,b))}

注意顺序:先除后乘,防止溢出:a / gcd(\(a,b\)) * b

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

✅ 小结

  1. 欧几里得算法的底层就是带余除法;
  2. GESP五级必考,最大公因数题目、约分、互素判断都用它;
  3. \(\gcd((a,b))=1) ⇔ (a,b)互质。

四、同余与剩余类

✅ 数学定义

若 mm 是正整数,(a,b)(a,b) 满足:

a≡b(modm)a \equiv b \pmod m

含义:a−ba-b 能够被 mm 整除;等价于 a mod m=b mod ma \bmod m = b \bmod m

剩余类(模m):把所有整数,按照模m的余数分成m组: [0],[1],[2],…,[m−1][0],[1],[2],\dots,[m-1],每一组就是一个剩余类。 例:模5剩余类: [0]=...,−5,0,5,10...[0]={...,-5,0,5,10...} [1]=...,−4,1,6,11...[1]={...,-4,1,6,11...}

✅ 同余运算性质(GESP会用到)

  1. 如果 a≡b(modm), c≡d(modm)a\equiv b \pmod m,\ c\equiv d\pmod m a+c≡b+d(modm)a+c \equiv b+d \pmod m a−c≡b−d(modm)a-c \equiv b-d \pmod m a×c≡b×d(modm)a\times c \equiv b\times d \pmod m

同余可以加减乘,不能随便除!

✅ 代码示例:判断同余、输出剩余类编号

#include <iostream>
using namespace std;
typedef long long ll;

// 修正版取模,保证余数非负
ll mod(ll a, ll m)
{
    ll r = a % m;
    if(r < 0) r += m;
    return r;
}

// 判断 a ≡ b (mod m)
bool isCongruent(ll a, ll b, ll m)
{
    return mod(a,m) == mod(b,m);
}

int main()
{
    ll \(a,b\),m;
    cout << "输入a b m:";
    cin >> a >> b >> m;
    if(isCongruent(\(a,b\),m))
    {
        cout << a << " ≡ " << b << " (mod " << m << ") 成立" << endl;
    }
    else
    {
        cout << "不成立" << endl;
    }
    cout << a << "属于模" << m << "的剩余类[" << mod(a,m) << "]" << endl;
    cout << b << "属于模" << m << "的剩余类[" << mod(b,m) << "]" << endl;
    return 0;
}

✅ 测试样例

输入:7 12 5 7 mod5=2,12 mod5=2 → 7 ≡ 12 (mod 5) 成立

✅ 小结

  1. 同余就是「除以m余数相等」;
  2. 剩余类就是按余数分组;
  3. 后续快速幂、模运算、不定方程都建立在同余上。

📚 串联思维导图(给学生板书用)

带余除法(a=bq+r) ↓ 推出 欧几里得辗转相除法(gcd)、同余定义 ↓ 算术基本定理(分解质因数) ↓ GESP真题:奇妙数字、B-smooth、原根、有限小数、最大公因数

📝 配套课堂小练习(4题)

  1. 带余除法:求 -20 ÷ 7 的标准余数
  2. 质因数分解:分解 720
  3. gcd:求 gcd(72,96)、lcm(72,96)
  4. 同余判断:19 和 44 在模 5 下是否同余?

0 条评论

目前还没有评论...