余数相同问题
- C语言代码
- C++ 代码
- Java代码
- Python代码
💐The Begin💐点点关注,收藏不迷路💐 |
已知三个正整数 a,b,c。
现有一个大于1的整数x,将其作为除数分别除a,b,c,得到的余数相同。
请问满足上述条件的x的最小值是多少?
数据保证x有解。
输入
一行,三个不大于1000000的正整数a,b,c,两个整数之间用一个空格隔开。
输出
一个整数,即满足条件的x的最小值。
样例输入
300 262 205
样例输出
19
C语言代码
#include <stdio.h>
#include <stdlib.h> // 引入abs函数所需头文件,用于求绝对值// 求两个数的最大公约数(辗转相除法)
int gcd(int a, int b) {a = abs(a); // 取绝对值,确保处理正数情况b = abs(b);while (b!= 0) {int temp = b;b = a % b;a = temp;}return a;
}int main() {int a, b, c;scanf("%d %d %d", &a, &b, &c); // 输入三个正整数a、b、cint diff1 = abs(a - b); // 计算a与b的差值的绝对值int diff2 = abs(b - c); // 计算b与c的差值的绝对值int diff3 = abs(a - c); // 计算a与c的差值的绝对值int gcd1 = gcd(diff1, diff2); // 求diff1和diff2的最大公约数int gcd2 = gcd(gcd1, diff3); // 再求前面得到的最大公约数与diff3的最大公约数int x = 2; // 从2开始找满足条件的x,因为题目要求x大于1while (x <= gcd2) { // 循环直到找到最小的满足条件的xif (gcd2 % x == 0) { // 如果gcd2能被x整除,说明x是满足条件的除数break;}x++;}printf("%d\n", x);return 0;
}
C++ 代码
#include <iostream>
#include <algorithm> // 引入abs函数所需头文件,用于求绝对值
using namespace std;// 求两个数的最大公约数(辗转相除法)
int gcd(int a, int b) {a = abs(a); // 取绝对值,确保处理正数情况b = abs(b);while (b!= 0) {int temp = b;b = a % b;a = temp;}return a;
}int main() {int a, b, c;cin >> a >> b >> c; // 输入三个正整数a、b、cint diff1 = abs(a - b); // 计算a与b的差值的绝对值int diff2 = abs(b - c); // 计算b与c的差值的绝对值int diff3 = abs(a - c); // 计算a与c的差值的绝对值int gcd1 = gcd(diff1, diff2); // 求diff1和diff2的最大公约数int gcd2 = gcd(gcd1, diff3); // 再求前面得到的最大公约数与diff3的最大公约数int x = 2; // 从2开始找满足条件的x,因为题目要求x大于1while (x <= gcd2) { // 循环直到找到最小的满足条件的xif (gcd2 % x == 0) { // 如果gcd2能被x整除,说明x是满足条件的除数break;}x++;}cout << x << endl;return 0;
}
Java代码
import java.util.Scanner;public class Main {// 求两个数的最大公约数(辗转相除法)static int gcd(int a, int b) {a = Math.abs(a); // 取绝对值,确保处理正数情况b = Math.abs(b);while (b!= 0) {int temp = b;b = a % b;a = temp;}return a;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int a = scanner.nextInt();int b = scanner.nextInt();int c = scanner.nextInt(); // 输入三个正整数a、b、cint diff1 = Math.abs(a - b); // 计算a与b的差值的绝对值int diff2 = Math.abs(b - c); // 计算b与c的差值的绝对值int diff3 = Math.abs(a - c); // 计算a与c的差值的绝对值int gcd1 = gcd(diff1, diff2); // 求diff1和diff2的最大公约数int gcd2 = gcd(gcd1, diff3); // 再求前面得到的最大公约数与diff3的最大公约数int x = 2; // 从2开始找满足条件的x,因为题目要求x大于1while (x <= gcd2) { // 循环直到找到最小的满足条件的xif (gcd2 % x == 0) { // 如果gcd2能被x整除,说明x是满足条件的除数break;}x++;}System.out.println(x);}
}
Python代码
a, b, c = map(int, input().split()) # 输入三个正整数a、b、cdiff1 = abs(a - b) # 计算a与b的差值的绝对值
diff2 = abs(b - c) # 计算b与c的差值的绝对值
diff3 = abs(a - c) # 计算a与c的差值的绝对值def gcd(a, b): # 定义求最大公约数的函数(辗转相除法)while b!= 0:a, b = b, a % breturn agcd1 = gcd(diff1, diff2) # 求diff1和diff2的最大公约数
gcd2 = gcd(gcd1, diff3) # 再求前面得到的最大公约数与diff3的最大公约数x = 2 # 从2开始找满足条件的x,因为题目要求x大于1
while x <= gcd2: # 循环直到找到最小的满足条件的xif gcd2 % x == 0: # 如果gcd2能被x整除,说明x是满足条件的除数breakx += 1print(x)
💐The End💐点点关注,收藏不迷路💐 |