第二十天：余数相同问题

每日一道C++题：余数相同问题

问题：已知三个正整数a，b，c。现有一个大于1的整数x，将其作为除数分别除a，b，c，得到的余数相同。请问满足上述条件的x的最小值是多少？数据保证x有解。

要求：输入一行，三个不大于1000000的正整数a，b，c，两个整数之间用一个空格隔开；输出一个整数，即满足条件的x的最小值。

• 设 a = k1 * x + r，b = k2 * x + r，c = k3 * x + r（其中 k1、k2、k3 为整数，r 为相同的余数）。那么 a - b = (k1 - k2) * x，b - c = (k2 - k3) * x，c - a = (k3 - k1) * x。这表明 x 是 |a - b|、|b - c|、|c - a| 的公约数。
• 要解决这个问题，我们需要按照以下详细步骤进行计算：

1. 计算差值的绝对值：

   • 首先，我们有三个原始数值 a, b, c
   • 计算三个差值：
     • |a - b|
     • |a - c|
     • |b - c|
   • 例如，若 a=15，b=20，c=25，则差值为5,10,5

2. 求最大公约数(GCD)：

   • 使用欧几里得算法求这三个差值的GCD
   • 先求前两个数的GCD，再将结果与第三个数求GCD
   • 对于示例5,10,5：
     • GCD(5,10)=5
     • GCD(5,5)=5

3. 判断GCD结果：

   • 如果GCD > 1：
     • 这个GCD就是满足条件的x的最小值
     • 示例中GCD=5，因此x=5
   • 如果GCD = 1：
     • 需要从2开始逐个测试整数
     • 找到能同时整除全部三个差值的第一个数
     • 例如，若差值为3,5,7(GCD=1)：
       • 2不满足
       • 3不满足(不能整除5)
       • …
       • 无解，说明x不存在

4. 验证结果：

   • 将求得的x代入验证：
     • 检查a%x、b%x、c%x是否相等
   • 对于x=5的示例：
     • 15%5=0
     • 20%5=0
     • 25%5=0
     • 满足条件

所以先求出这三个差值的绝对值，然后计算它们的最大公约数。如果最大公约数大于 1，那么这个最大公约数就是满足条件的 x 的最小值；如果最大公约数为 1，则需要从 2 开始逐个检查整数，找到第一个能同时整除这三个差值绝对值的数，即为所求的 x 的最小值。

#include <iostream>
#include <cmath>
using namespace std;// 计算两个数的最大公约数
int gcd(int m, int n) {while (n!= 0) {int temp = n;n = m % n;m = temp;}return m;
}int main() {int a, b, c;cin >> a >> b >> c;int diff1 = abs(a - b);int diff2 = abs(b - c);int diff3 = abs(c - a);int result = gcd(gcd(diff1, diff2), diff3);if (result == 1) {for (int i = 2; ; i++) {if (diff1 % i == 0 && diff2 % i == 0 && diff3 % i == 0) {result = i;break;}}}cout << result << endl;return 0;
}

多个数的情况

寻找使多个数同余的最小整数 x 的算法详解

问题描述

给定 n 个正整数（n ≥ 3），要求找到一个大于 1 的最小整数 x，使得这 n 个数除以 x 的余数相同。换句话说，我们需要找到一个最小的 x > 1，使得对于所有给定的数 a₁, a₂, …, aₙ，都有 aᵢ ≡ r (mod x) 对于某个固定的余数 r。

详细求解步骤

1. 计算两两之差的绝对值

   • 对于给定的 n 个数 a₁, a₂, …, aₙ，计算所有可能的两两之差的绝对值，即 |aᵢ - aⱼ|，其中 1 ≤ i < j ≤ n。
   • 例如，对于数列 [5, 17, 29]，计算 |5-17|=12，|5-29|=24，|17-29|=12，得到差值集合 {12, 24, 12}。

2. 求这些差值的最大公约数（GCD）

   • 计算上一步得到的所有差值的最大公约数 d。
   • 继续上面的例子，GCD(12, 24, 12) = 12。
   • 如果所有差值都是 0（即所有数相同），则任何大于 1 的 x 都满足条件，此时最小 x=2。

3. 确定解 x

   • 如果 d > 1，则 x = d 就是满足条件的最小解。因为：
     • d 是所有差值的公约数，所以 aᵢ ≡ aⱼ (mod d)，即所有数模 d 的余数相同。
     • d 是最大的这样的数，因此也是满足条件的最小数。
   • 如果 d = 1，则不存在大于 1 的整数能整除所有差值，此时需要从 2 开始逐个检查最小的满足条件的 x：
     • 检查 x=2：计算所有数模 2 的余数是否相同。
     • 检查 x=3：同上。
     • 依此类推，直到找到满足条件的最小 x > 1。

4. 算法终止条件

   • 由于 x 必须大于 1，且对于任何数列至少存在 x=2 可能满足条件（虽然不一定），所以算法总能终止。
   • 最坏情况下（如互质的数列），可能需要检查到 x=最大数-最小数。

示例说明

• 示例1：数列 [5, 17, 29]

  • 差值：12, 24, 12
  • GCD=12 → x=12
  • 验证：5≡5, 17≡5, 29≡5 (mod 12)

• 示例2：数列 [3, 5, 7]

  • 差值：2, 4, 2
  • GCD=2 → x=2
  • 验证：3≡1, 5≡1, 7≡1 (mod 2)

• 示例3：数列 [6, 10, 15]

  • 差值：4, 9, 5
  • GCD=1 → 需要逐个检查
  • x=2: 6≡0, 10≡0, 15≡1 → 不满足
  • x=3: 6≡0, 10≡1, 15≡0 → 不满足
  • x=4: 6≡2, 10≡2, 15≡3 → 不满足
  • x=5: 6≡1, 10≡0, 15≡0 → 不满足
  • 最终无解（实际上这个数列不存在满足条件的 x>1）

数学原理

这个算法基于以下数学观察：

• 如果 a ≡ r (mod x) 且 b ≡ r (mod x)，则 x 必须整除 |a-b|。
• 因此，x 必须整除所有两两差值，最大的这样的 x 就是这些差值的 GCD。
• 当 GCD=1 时，说明这些数互质，只能通过逐个检查来寻找可能的 x。

复杂度分析

• 计算差值：O(n²) 时间
• 计算 GCD：O(k log m)，其中 k 是差值个数，m 是最大差值
• 逐个检查：最坏 O(m) 次检查，每次 O(n)
• 总复杂度：最坏 O(n² + n·m)

应用场景

• 密码学中的同余关系分析
• 数据校验和错误检测
• 计算机科学中的散列函数设计
• 数学竞赛中的数论问题求解

该算法有效地利用了数论中同余和最大公约数的性质，通过系统化的步骤解决了寻找最小同余模数的问题。### 寻找使多个数同余的最小整数 x 的算法详解

问题描述

给定 n 个正整数（n ≥ 3），要求找到一个大于 1 的最小整数 x，使得这 n 个数除以 x 的余数相同。换句话说，我们需要找到一个最小的 x > 1，使得对于所有给定的数 a₁, a₂, …, aₙ，都有 aᵢ ≡ r (mod x) 对于某个固定的余数 r。

详细求解步骤

1. 计算两两之差的绝对值

   • 对于给定的 n 个数 a₁, a₂, …, aₙ，计算所有可能的两两之差的绝对值，即 |aᵢ - aⱼ|，其中 1 ≤ i < j ≤ n。
   • 例如，对于数列 [5, 17, 29]，计算 |5-17|=12，|5-29|=24，|17-29|=12，得到差值集合 {12, 24, 12}。

2. 求这些差值的最大公约数（GCD）

   • 计算上一步得到的所有差值的最大公约数 d。
   • 继续上面的例子，GCD(12, 24, 12) = 12。
   • 如果所有差值都是 0（即所有数相同），则任何大于 1 的 x 都满足条件，此时最小 x=2。

3. 确定解 x

   • 如果 d > 1，则 x = d 就是满足条件的最小解。因为：
     • d 是所有差值的公约数，所以 aᵢ ≡ aⱼ (mod d)，即所有数模 d 的余数相同。
     • d 是最大的这样的数，因此也是满足条件的最小数。
   • 如果 d = 1，则不存在大于 1 的整数能整除所有差值，此时需要从 2 开始逐个检查最小的满足条件的 x：
     • 检查 x=2：计算所有数模 2 的余数是否相同。
     • 检查 x=3：同上。
     • 依此类推，直到找到满足条件的最小 x > 1。

4. 算法终止条件

   • 由于 x 必须大于 1，且对于任何数列至少存在 x=2 可能满足条件（虽然不一定），所以算法总能终止。
   • 最坏情况下（如互质的数列），可能需要检查到 x=最大数-最小数。

示例说明

• 示例1：数列 [5, 17, 29]

  • 差值：12, 24, 12
  • GCD=12 → x=12
  • 验证：5≡5, 17≡5, 29≡5 (mod 12)

• 示例2：数列 [3, 5, 7]

  • 差值：2, 4, 2
  • GCD=2 → x=2
  • 验证：3≡1, 5≡1, 7≡1 (mod 2)

• 示例3：数列 [6, 10, 15]

  • 差值：4, 9, 5
  • GCD=1 → 需要逐个检查
  • x=2: 6≡0, 10≡0, 15≡1 → 不满足
  • x=3: 6≡0, 10≡1, 15≡0 → 不满足
  • x=4: 6≡2, 10≡2, 15≡3 → 不满足
  • x=5: 6≡1, 10≡0, 15≡0 → 不满足
  • 最终无解（实际上这个数列不存在满足条件的 x>1）

数学原理

这个算法基于以下数学观察：

• 如果 a ≡ r (mod x) 且 b ≡ r (mod x)，则 x 必须整除 |a-b|。
• 因此，x 必须整除所有两两差值，最大的这样的 x 就是这些差值的 GCD。
• 当 GCD=1 时，说明这些数互质，只能通过逐个检查来寻找可能的 x。

复杂度分析

• 计算差值：O(n²) 时间
• 计算 GCD：O(k log m)，其中 k 是差值个数，m 是最大差值
• 逐个检查：最坏 O(m) 次检查，每次 O(n)
• 总复杂度：最坏 O(n² + n·m)

应用场景

• 密码学中的同余关系分析
• 数据校验和错误检测
• 计算机科学中的散列函数设计
• 数学竞赛中的数论问题求解

该算法有效地利用了数论中同余和最大公约数的性质，通过系统化的步骤解决了寻找最小同余模数的问题。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;// 计算两个数的最大公约数
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}int main() {int n;cout << "请输入整数个数 n: ";cin >> n;vector<int> numbers(n);cout << "请输入 " << n << " 个正整数: ";for (int i = 0; i < n; ++i) {cin >> numbers[i];}// 计算所有数对的差值vector<int> diffs;for (int i = 0; i < n - 1; ++i) {for (int j = i + 1; j < n; ++j) {diffs.push_back(abs(numbers[i] - numbers[j]));}}// 计算所有差值的最大公约数int result = diffs[0];for (size_t i = 1; i < diffs.size(); ++i) {result = gcd(result, diffs[i]);}// 如果最大公约数为1，寻找最小满足条件的xif (result == 1) {for (int x = 2; ; ++x) {bool is_valid = true;for (int diff : diffs) {if (diff % x != 0) {is_valid = false;break;}}if (is_valid) {result = x;break;}}}cout << "满足条件的 x 的最小值是: " << result << endl;return 0;
}

求所有满足条件的 x

问题描述

给定三个正整数 a、b、c，找出所有大于 1 的整数 x，使得 a、b、c 分别除以 x 得到的余数相同。

算法思路

1. 余数相同的条件：如果 a、b、c 除以 x 的余数相同，那么 a、b、c 可以表示为：

   • a = k₁ * x + r
   • b = k₂ * x + r
   • c = k₃ * x + r
     其中，k₁、k₂、k₃ 是整数，r 是相同的余数（0 ≤ r < x）。

2. 差值分析：

   • 由上述表达式可得：
     • a - b = (k₁ - k₂) * x
     • b - c = (k₂ - k₃) * x
     • c - a = (k₃ - k₁) * x
       这说明 a - b、b - c、c - a 都是 x 的倍数。

3. 最大公约数（GCD）：

   • 设：
     • d₁ = |a - b|
     • d₂ = |b - c|
     • d₃ = |c - a|
   • 则 x 必须是 d₁、d₂、d₃ 的公约数。
   • 计算 g = gcd(d₁, d₂, d₃)，g 是 d₁、d₂、d₃ 的最大公约数。

4. 求解 x：

   • x 必须是 g 的因数，且 x > 1。
   • 因此，找出 g 的所有大于 1 的因数，这些因数就是所有满足条件的 x。

示例

假设 a = 10, b = 4, c = 7：

1. 计算差值：
   • d₁ = |10 - 4| = 6
   • d₂ = |4 - 7| = 3
   • d₃ = |7 - 10| = 3
2. 计算 g = gcd(6, 3, 3) = 3。
3. g 的大于 1 的因数为 3。
   • 验证：
     • 10 ÷ 3 余 1
     • 4 ÷ 3 余 1
     • 7 ÷ 3 余 1
   • 余数相同，满足条件。

实现步骤

1. 计算 |a - b|、|b - c|、|c - a|。
2. 求这三个数的最大公约数 g。
3. 找出 g 的所有大于 1 的因数，即为满足条件的 x。

应用场景

• 密码学：用于构造特定性质的模运算条件。
• 数学竞赛：常见于数论问题。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;// 计算两个数的最大公约数
int gcd(int m, int n) {while (n!= 0) {int temp = n;n = m % n;m = temp;}return m;
}// 找出一个数的所有大于1的因数
vector<int> findFactors(int num) {vector<int> factors;for (int i = 2; i <= num; i++) {if (num % i == 0) {factors.push_back(i);}}return factors;
}int main() {int a, b, c;cin >> a >> b >> c;int diff1 = abs(a - b);int diff2 = abs(b - c);int diff3 = abs(c - a);int gcdValue = gcd(gcd(diff1, diff2), diff3);vector<int> results = findFactors(gcdValue);cout << "满足条件的所有 x 是: ";for (int x : results) {cout << x << " ";}cout << endl;return 0;
}

考虑余数范围限制

• 给定三个正整数 a、b、c，找到一个大于 1 的整数 x，使得 a、b、c 分别除以 x 得到的余数相同，且余数在某个给定范围 [low, high] 内（0 <= low <= high < x），求 x 的最小值。
• 在原方法基础上，当找到可能的 x 后，检查 a % x、b % x、c % x 是否都在 [low, high] 范围内。如果不在，则继续寻找下一个满足条件的 x。

#include <iostream>
#include <cmath>
using namespace std;// 计算两个数的最大公约数
int gcd(int m, int n) {while (n!= 0) {int temp = n;n = m % n;m = temp;}return m;
}int main() {int a, b, c, low, high;cin >> a >> b >> c >> low >> high;int diff1 = abs(a - b);int diff2 = abs(b - c);int diff3 = abs(c - a);int result = gcd(gcd(diff1, diff2), diff3);if (result == 1) {for (int i = 2; ; i++) {if (diff1 % i == 0 && diff2 % i == 0 && diff3 % i == 0) {int rem1 = a % i, rem2 = b % i, rem3 = c % i;if (rem1 >= low && rem1 <= high && rem2 >= low && rem2 <= high && rem3 >= low && rem3 <= high) {result = i;break;}}}} else {while (true) {int rem1 = a % result, rem2 = b % result, rem3 = c % result;if (rem1 >= low && rem1 <= high && rem2 >= low && rem2 <= high && rem3 >= low && rem3 <= high) {break;}result--;while (result > 1 && (diff1 % result!= 0 || diff2 % result!= 0 || diff3 % result!= 0)) {result--;}if (result == 1) {for (int i = 2; ; i++) {if (diff1 % i == 0 && diff2 % i == 0 && diff3 % i == 0) {int rem1 = a % i, rem2 = b % i, rem3 = c % i;if (rem1 >= low && rem1 <= high && rem2 >= low && rem2 <= high && rem3 >= low && rem3 <= high) {result = i;break;}}}break;}}}cout << "满足条件的 x 的最小值是: " << result << endl;return 0;
}