2039: 【作】余数相同问题

内存限制：256 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：2 解决：2

题目描述

已知三个正整数a，b，c。现有一个大于1的整数x，将其作为除数分别除a，b，c，得到的余数相同。

请问满足上述条件的x的最小值是多少？数据保证x有解。

输入

一行，三个不大于1000000的正整数a，b，c，两个整数之间用一个空格隔开。

输出

一个整数，即满足条件的x的最小值。

样例输入 复制 

300 262 205

样例输出 复制 

19

提示

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;

    // 同余定理：余数相同，则两数之差能被x整除，先求两两差值绝对值
    int d1 = abs(a - b);
    int d2 = abs(a - c);
    int d3 = abs(b - c);

    int min_x;
    // 根据数论要求，x必须大于1，从2开始从小到大找，第一个符合条件就是最小值
    for (int x = 2; ; x++)
    {
        // 判断x是否同时整除三个差值（同余判定条件）
        if (d1 % x == 0 && d2 % x == 0 && d3 % x == 0)
        {
            min_x = x;
            break;
        }
    }

    cout << min_x << endl;
    return 0;
}

#include <iostream>
#include <cmath>
using namespace std;

// 求两个数最大公约数（辗转相除法，数论基础算法）
int gcd(int m, int n)
{
    while (n != 0)
    {
        int t = m % n;
        m = n;
        n = t;
    }
    return m;
}

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    int d1 = abs(a - b);
    int d2 = abs(a - c);
    int d3 = abs(b - c);

    // 先求三个差值的最大公约数，所有合法x都≤g
    int g1 = gcd(d1, d2);
    int g = gcd(g1, d3);

    int ans;
    for (int x = 2; x <= g; x++)
    {
        if (d1 % x == 0 && d2 % x == 0 && d3 % x == 0)
        {
            ans = x;
            break;
        }
    }
    cout << ans;
    return 0;
}

来源/分类

提交提交记录统计露一手!