当前位置：首页 > ai >正文

百度之星2021——BD202104 萌新

ai 2025/6/22 15:01:23

在这里插入图片描述
输入格式：
本题有多组测试数据。
第一行一个数 T (1 ≤ T ≤ 1000) 表示一共有 T 组数据。对于每一组数据，输入一行两个数 a,b (1 ≤ a,b ≤ 1000000000)。
输出格式：
对每组数据，输出一行两个数分别表示最小与最大的 c，如果不存在满足题意的 c，则输出一行两个 -1。

样例1：

样例2：

关键思路：

重点1：

（同余的定义）：a mod c = b mod c, 那么a-b是c的倍数，即 c | (a - b)。
分析：
模运算：a mod c 表示 a 除以 c 的余数，可以表示为 a = k * c + r，其中 0 ≤ r < c；
那么有

•	a mod c = r      ⇒       a = k * c + r
•	b mod c = r      ⇒       b = m * c + r

因此，a - b = (k - m) * c，即 a - b 是 c 的倍数。

重点2：

可以通过枚举a-b的因子去寻找最小和最大的 c 。

注意：当a=b的情况，此时a-b=0，因此需要单独处理：

如果a=b=1，则答案为-1，-1，
否则答案为2，a

具体C++代码为：

#include<bits/stdc++.h> 
#include <iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<math.h>
#include <string.h>
using namespace std;
using namespace std;int main( )
{int n;cin>>n;while(n--){long long int a,b;cin>>a>>b;long long int cmax=abs(a-b);long long int cmin=0;if(cmax==0&&a>=2)cout<<2<<" "<<a<<endl;else if(cmax>=2){for(int i=2;i*i<=cmax;i++){if(cmax%i==0){cmin=i;break;}}if(cmin==0)cmin=cmax;cout<<cmin<<" "<<cmax<<endl;}else cout<<-1<<" "<<-1<<endl;}return 0;
}

Python代码：

import mathdef main():import sysinput = sys.stdin.read  # 使用更可靠的输入方式data = input().split()idx = 0n = int(data[idx])idx += 1for _ in range(n):a = int(data[idx])b = int(data[idx + 1])idx += 2cmax = abs(a - b)cmin = 0if cmax == 0 and a >= 2:print(2, a)elif cmax >= 2:cmin = 0# 改用 math.sqrt 兼容旧版 Pythonsqrt_cmax = int(math.sqrt(cmax)) + 1for i in range(2, sqrt_cmax):if cmax % i == 0:cmin = ibreakif cmin == 0:cmin = cmaxprint(cmin, cmax)else:print(-1, -1)if __name__ == "__main__":main()

Java代码：

import java.util.Scanner;
import java.lang.Math;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();while (n-- > 0) {long a = scanner.nextLong();long b = scanner.nextLong();long cmax = Math.abs(a - b);long cmin = 0;if (cmax == 0 && a >= 2) {System.out.println("2 " + a);} else if (cmax >= 2) {for (long i = 2; i * i <= cmax; i++) {if (cmax % i == 0) {cmin = i;break;}}if (cmin == 0) {cmin = cmax;}System.out.println(cmin + " " + cmax);} else {System.out.println("-1 -1");}}scanner.close();}
}

查看全文

http://www.xdnf.cn/news/13177.html