余数相同问题

题目描述

已知三个正整数 a, b, c，求最小的大于 1 的整数 x，使得 a, b, c 分别除以 x 所得余数相同。数据保证有解。

思路

同余意味着 x 整除任意两数之差，因此 x 必须整除 gcd(a-b, b-c)。当 a=b=c 时答案为 2；否则答案是该 gcd 的最小大于 1 的因子，直接枚举到 √g 即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 17:43
# update_at: 2026-09-29 17:48

import sys
from math import gcd


def solve() -> None:
    a, b, c = map(int, sys.stdin.buffer.read().split())

    # 同余条件 a%x == b%x == c%x ⇔ x 同时整除两个差 a-b 与 b-c
    diff_ab = a - b  # 题面的 a-b，等于 0 时对约束无贡献
    diff_bc = b - c  # 题面的 b-c，同理
    g = gcd(diff_ab, diff_bc) or 2  # 所有可行 x 的公约束；a=b=c 时为 0，任何 x>1 都可行，答案 2

    x = next(i for i in range(2, g + 1) if g % i == 0)  # g 的最小大于 1 的因子

    print(x)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 00:27
 * update_at: 2026-10-05 00:27
 */
#include <iostream>
#include <numeric>
using namespace std;

typedef long long ll;

ll a, b, c;

// 求 x 的最小大于 1 的因子
ll min_factor(ll x) {
    for (ll i = 2; i * i <= x; ++i)
        if (x % i == 0) return i;
    return x; // x 本身是素数
}

int main() {
    cin >> a >> b >> c;
    ll g = gcd(a - b, b - c); // C++17 gcd 返回非负
    if (g == 0) {             // a == b == c 时任意 x > 1 都合法
        cout << 2 << endl;
        return 0;
    }
    cout << min_factor(g) << endl;
    return 0;
}

目录

题目描述

思路

参考代码