- C++
同余与剩余类 C++ 教程(GESP五级)
- @ 2026-10-21 22:41:02
同余与剩余类 C++ 教程(GESP五级)
前置知识:带余除法、
long long、取模运算 适用:GESP五级数论考点
一、数学概念
1. 同余定义
设 是正整数。如果整数 除以 的余数相等,则称 a 和 b 模 m 同余,记作:
等价条件:
$$m \mid (a-b) \quad \text{也就是:}a-b\text{ 能被}m\text{整除}$$✅ 例子: 余2, 余2
2. 剩余类(模m)
把全体整数按照模 的余数分成 组,每一组叫做一个模m剩余类:
代表所有满足 的整数集合。 例:模5
一句话记忆:同一个剩余类里面所有数,模m同余。
3. 同余的运算性质(GESP常考)
若
⚠️ 重点大坑:同余不能随便两边同时除以一个数!
4. C++原生取模的坑
C++ % 运算符,结果符号和被除数一致。
数论里要求余数 ,负数直接%会得到负余数,不符合同余定义,必须修正。
例: 在C++得到 -2,数论标准余数应该是 3。
修正公式:
r = a % m;
if (r < 0) r += m;
二、基础函数封装
#include <iostream>
using namespace std;
typedef long long ll;
// 修正取模,保证返回 0 <= r < m
ll mod(ll a, ll m)
{
ll r = a % m;
if (r < 0)
{
r += m;
}
return r;
}
// 判断 a ≡ b (mod m) 是否成立
bool congruent(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;
ll ra = mod(a, m);
ll rb = mod(b, m);
cout << a << " mod " << m << " = " << ra << endl;
cout << b << " mod " << m << " = " << rb << endl;
if (congruent(a, b, m))
{
cout << a << " ≡ " << b << " (mod " << m << ") 成立" << endl;
}
else
{
cout << a << " ≡ " << b << " (mod " << m << ") 不成立" << endl;
}
return 0;
}
样例测试1:
输入:7 12 5
输出:
7 mod 5 = 2
12 mod 5 = 2
7 ≡ 12 (mod 5) 成立
样例测试2(负数):
输入:-7 3 5
输出:
-7 mod 5 = 3
3 mod 5 = 3
-7 ≡ 3 (mod 5) 成立
三、例题1:输出一个数所属的剩余类编号
题目:输入整数a、模数m,输出a属于模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;
}
int main()
{
ll a, m;
cin >> a >> m;
ll r = mod(a, m);
cout << a << " 属于模" << m << "的剩余类 [" << r << "]" << endl;
return 0;
}
输入:-20 7
输出:-20 属于模7的剩余类 [1]
四、例题2:同余加法、乘法运算演示
验证同余加减乘性质:输入(a,b),c,d,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;
}
int main()
{
ll \(a,b\),c,d,m;
cin >> a >> b >> c >> d >> m;
ll add1 = mod(a + c, m);
ll add2 = mod(b + d, m);
ll mul1 = mod(a * c, m);
ll mul2 = mod(b * d, m);
cout << "(a+c) mod m = " << add1 << endl;
cout << "(b+d) mod m = " << add2 << endl;
cout << "(a*c) mod m = " << mul1 << endl;
cout << "(b*d) mod m = " << mul2 << endl;
return 0;
}
输入:7 12 3 8 5
,模5都为0;
,模5都为1。
提示:大数相乘会爆long long,后面进阶要学快速幂取模,五级了解即可。
五、课堂小结(板书背诵版)
- 同余 = 除以m余数相等;
- 剩余类就是按余数分组,同余的数在同一个剩余类;
- C++负数取模有坑,一定要写修正mod函数;
- 同余支持加法、减法、乘法,不支持直接除法。
六、配套课堂小练习
- 判断 是否成立?
- 求 在模5下属于哪个剩余类?
- 已知 ,计算 和
七、拓展预告(五级后面)
同余是快速幂、欧拉定理、原根判断的基础,4114原根判断一题,大量依赖同余判定。
0 条评论
目前还没有评论...