中等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 的余数分类​​。判断时注意负数与溢出的坑,利用"同奇偶得偶、有偶则积偶"的规律,很多计数与判定问题都能被简化。

同类知识点