- C++
数论四大基础 C++ 教程(GESP五级适用)
- @ 2026-10-21 22:35:14
数论四大基础 C++ 教程(GESP五级适用)
包含:带余除法、算术基本定理、欧几里得算法、同余与剩余类
面向GESP5级,全部带可直接运行代码、逐行注释、例题、课堂小结,适合上课讲
前置说明
数据范围:GESP一般到 ,统一使用 long long;
头文件统一:
#include <iostream>
using namespace std;
typedef long long ll;
一、带余除法(除法算式:)
✅ 数学定义(带余除法)
对任意整数 、正整数 ,存在唯一一对整数 ,满足:
- :被除数
- :除数
- :商
- :余数
重点:余数一定 ≥0,并且严格小于除数! 例:,商3,余数2; ,余数不能是负数。
✅ C++ 注意坑
C++ 中 % 取模,负数的取模结果符号和被除数一致,和数论里带余除法要求的 不一样!
👉 需要写函数修正,得到标准非负余数。
✅ 代码:求标准带余除法的商、余数
#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
✅ 小结
- 带余除法是所有数论的地基,gcd、同余都建立在它上面;
- C++原生
%不能直接当数论余数,负数必须修正。
二、算术基本定理(唯一分解定理)
✅ 数学定义
任何大于1的正整数 ,都可以唯一分解成素数乘积(不计顺序):
是互不相同质数, 为指数。
就是我们奇妙数字一题用到的定理!
✅ 算法思路:试除法分解质因数
- 从2枚举到 ;
- 如果 能整除 ,统计指数,不断把n除以i;
- 循环结束,如果剩下的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
✅ 小结
- 分解结果唯一;
- GESP高频考点:奇妙数字、B-smooth数、有限小数判断全部依赖它;
- 适合 以内,i*i 要开long long,防止溢出。
三、欧几里得算法(辗转相除法,求gcd最大公因数)
✅ 数学依据(带余除法推导)
一直递归,直到余数为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
注意顺序:先除后乘,防止溢出:
a / gcd(\(a,b\)) * b
ll lcm(ll a, ll b)
{
return a / gcd(\(a,b\)) * b;
}
✅ 小结
- 欧几里得算法的底层就是带余除法;
- GESP五级必考,最大公因数题目、约分、互素判断都用它;
- \(\gcd((a,b))=1) ⇔ (a,b)互质。
四、同余与剩余类
✅ 数学定义
若 是正整数, 满足:
含义: 能够被 整除;等价于
剩余类(模m):把所有整数,按照模m的余数分成m组: ,每一组就是一个剩余类。 例:模5剩余类:
✅ 同余运算性质(GESP会用到)
- 如果
同余可以加减乘,不能随便除!
✅ 代码示例:判断同余、输出剩余类编号
#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) 成立
✅ 小结
- 同余就是「除以m余数相等」;
- 剩余类就是按余数分组;
- 后续快速幂、模运算、不定方程都建立在同余上。
📚 串联思维导图(给学生板书用)
带余除法(a=bq+r) ↓ 推出 欧几里得辗转相除法(gcd)、同余定义 ↓ 算术基本定理(分解质因数) ↓ GESP真题:奇妙数字、B-smooth、原根、有限小数、最大公因数
📝 配套课堂小练习(4题)
- 带余除法:求 -20 ÷ 7 的标准余数
- 质因数分解:分解 720
- gcd:求 gcd(72,96)、lcm(72,96)
- 同余判断:19 和 44 在模 5 下是否同余?