CF1872C.Non-coprime Split
普及-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given two integers l≤r. You need to find positive integers a and b such that the following conditions are simultaneously satisfied:
- l≤a+b≤r
- gcd(a,b)=1
or report that they do not exist.
gcd(a,b) denotes the greatest common divisor of numbers a and b. For example, gcd(6,9)=3, gcd(8,9)=1, gcd(4,2)=2.
给你两个整数 l≤r。你需要找出正整数 a 和 b,使得以下条件同时成立:
- l≤a+b≤r
- gcd(a,b)=1
若不存在满足条件的 a 和 b,则报告无解。
gcd(a,b) 表示数字 a 和 b 的最大公约数。例如,gcd(6,9)=3,gcd(8,9)=1,gcd(4,2)=2。
输入格式
The first line of the input contains an integer t (1≤t≤500) — the number of test cases.
Then the descriptions of the test cases follow.
The only line of the description of each test case contains 2 integers l,r (1≤l≤r≤107).
输入的第一行包含一个整数 t(1≤t≤500)—— 表示测试用例的数量。
接下来是各测试用例的描述。
每个测试用例的描述仅有一行,包含两个整数 l,r(1≤l≤r≤107)。
输出格式
For each test case, output the integers a,b that satisfy all the conditions on a separate line. If there is no answer, instead output a single number −1.
If there are multiple answers, you can output any of them.
对于每个测试用例,在单独一行中输出满足所有条件的整数 a,b。如果没有满足条件的解,则输出单个数字 −1。
如果存在多个解,可以输出其中任意一个。
输入输出样例
输入#1
11 11 15 1 3 18 19 41 43 777 777 8000000 10000000 2000 2023 1791791 1791791 1 4 2 3 9840769 9840769
输出#1
6 9 -1 14 4 36 6 111 666 4000000 5000000 2009 7 -1 2 2 -1 6274 9834495
说明/提示
In the first test case, 11≤6+9≤15, gcd(6,9)=3, and all conditions are satisfied. Note that this is not the only possible answer, for example, 4,10,5,10,6,6 are also valid answers for this test case.
In the second test case, the only pairs a,b that satisfy the condition 1≤a+b≤3 are 1,1,1,2,2,1, but in each of these pairs gcd(a,b) equals 1, so there is no answer.
In the third sample test, gcd(14,4)=2.
在第一个测试用例中,11≤6+9≤15,gcd(6,9)=3,所有条件均满足。注意,这并非唯一的可能答案,例如 {4,10}、{5,10}、{6,6} 对该测试用例而言也是有效的答案。
在第二个测试用例中,唯一满足条件 1≤a+b≤3 的数对 {a,b} 是 {1,1}、{1,2}、{2,1},但这些数对中每一对的 gcd(a,b) 均为 1,因此无解。
在第三个样例测试中,gcd(14,4)=2。
输入解题思路,AI测评打分。不知道怎么写?