中等C++3 分钟994 字
初等数论:奇偶性
奇偶性是初等数论中最基础也最常用的性质。很多题目看似复杂,抓住奇偶性后一行就能判断——它是竞赛里的"第一直觉"。
定义
- 偶数:能被 2 整除的整数,形式为
2k(k 为整数) - 奇数:不能被 2 整除的整数,形式为
2k + 1
用 C++ 判断:
cpp
bool isEven(int n) {
return n % 2 == 0;
}
注意:C++ 中负数取模会得到负值,-3 % 2 == -1,所以判断奇数不能写 n % 2 == 1,应写 n % 2 != 0。更快的写法是用位运算:
cpp
if ((n & 1) == 0) { /* 偶数 */ }
else { /* 奇数 */ }
Python 的 % 对负数返回非负余数,-3 % 2 得到 1,可以直接判断:
python
n = int(input())
print('偶数' if n % 2 == 0 else '奇数')
奇偶性的运算规律
| 运算 | 结果 |
|---|---|
| 偶 ± 偶 | 偶 |
| 奇 ± 奇 | 偶 |
| 奇 ± 偶 | 奇 |
| 偶 × 偶 | 偶 |
| 偶 × 奇 | 偶 |
| 奇 × 奇 | 奇 |
一句话记忆:乘法中只要有一个偶数,结果必为偶数;加法中"同奇偶得偶,异奇偶得奇"。
经典结论
1. 奇数的平方仍是奇数,偶数的平方仍是偶数
因为 (2k+1)² = 4k² + 4k + 1,除以 2 余 1。
2. 完全平方数除以 4 的余数只能是 0 或 1
这是判断"某数能不能是完全平方数"的快筛。例如证明"形如 4k+2 的数不可能是完全平方数":
cpp
// n 是完全平方数 => n % 4 只能是 0 或 1
if (n % 4 == 2 || n % 4 == 3) {
cout << "不可能是完全平方数";
}
3. 连续整数之和的奇偶性
1 + 2 + ... + n = n(n+1)/2。其中 n 与 n+1 一奇一偶,乘积必为偶数,故和一定是整数。
4. 奇偶性在奇偶校验中的应用
统计一段数据中"1"的个数是奇是偶,可以检测传输错误——这是校验码的原理,也是位运算中 popcount & 1 的用途。
应用:判断两数之和/积的奇偶
cpp
#include <iostream>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
// 和为偶数 <=> 两数同奇偶 <=> (a - b) 是偶数
cout << ((a - b) % 2 == 0 ? "和为偶数" : "和为奇数") << endl;
// 积为奇数 <=> 两数都是奇数
cout << ((a % 2 != 0 && b % 2 != 0) ? "积为奇数" : "积为偶数") << endl;
return 0;
}
Python 版本:
python
a, b = map(int, input().split())
print("和为偶数" if (a + b) % 2 == 0 else "和为奇数")
print("积为奇数" if a % 2 == 1 and b % 2 == 1 else "积为偶数")
应用:奇偶性配对
题目:有 n 个整数,每次可以选两个数相加,求最多能组成多少对和为偶数。
思路:和为偶数要求两数同奇偶,所以把奇数和偶数分别计数,各自内部两两配对即可:
cpp
long long odd = 0, even = 0;
for (int i = 0; i < n; i++) {
int x; cin >> x;
if (x % 2 != 0) odd++;
else even++;
}
// 每两个同奇偶的数配成一对
long long ans = (odd / 2) + (even / 2);
cout << ans;
常见陷阱
- 负数取模:C++ 中
-3 % 2 == -1,判断奇数要用!= 0而不是== 1。 - 溢出:
(a + b) % 2在大数相加时可能溢出,改用(a - b) % 2或直接比较a % 2 == b % 2更安全。 - 浮点数不能用奇偶性:奇偶性是整数概念,
3.0不是奇数也不是偶数。
小结
奇偶性本质是模 2 的余数分类。判断时注意负数与溢出的坑,利用"同奇偶得偶、有偶则积偶"的规律,很多计数与判定问题都能被简化。