CF1872C.Non-coprime Split

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given two integers l≤rl \le r. You need to find positive integers aa and bb such that the following conditions are simultaneously satisfied:

  • l≤a+b≤rl \le a + b \le r
  • gcd⁡(a,b)≠1\gcd(a, b) \neq 1

or report that they do not exist.

gcd⁡(a,b)\gcd(a, b) denotes the greatest common divisor of numbers aa and bb. For example, gcd⁡(6,9)=3\gcd(6, 9) = 3, gcd⁡(8,9)=1\gcd(8, 9) = 1, gcd⁡(4,2)=2\gcd(4, 2) = 2.

给你两个整数 l≤rl \le r。你需要找出正整数 aa 和 bb,使得以下条件同时成立:

  • l≤a+b≤rl \le a + b \le r
  • gcd⁡(a,b)≠1\gcd(a, b) \neq 1

若不存在满足条件的 aa 和 bb,则报告无解。

gcd⁡(a,b)\gcd(a, b) 表示数字 aa 和 bb 的最大公约数。例如,gcd⁡(6,9)=3\gcd(6, 9) = 3,gcd⁡(8,9)=1\gcd(8, 9) = 1,gcd⁡(4,2)=2\gcd(4, 2) = 2。

输入格式

The first line of the input contains an integer tt (1≤t≤5001 \le t \le 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 22 integers l,rl, r (1≤l≤r≤1071 \le l \le r \le 10^7).

输入的第一行包含一个整数 tt(1≤t≤5001 \le t \le 500)—— 表示测试用例的数量。

接下来是各测试用例的描述。

每个测试用例的描述仅有一行,包含两个整数 l,rl, r(1≤l≤r≤1071 \le l \le r \le 10^7)。

输出格式

For each test case, output the integers a,ba, b that satisfy all the conditions on a separate line. If there is no answer, instead output a single number −1-1.

If there are multiple answers, you can output any of them.

对于每个测试用例,在单独一行中输出满足所有条件的整数 a,ba, b。如果没有满足条件的解,则输出单个数字 −1-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≤1511 \le 6 + 9 \le 15, gcd⁡(6,9)=3\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{4, 10}, {5, 10}, {6, 6} are also valid answers for this test case.

In the second test case, the only pairs a,b{a, b} that satisfy the condition 1≤a+b≤31 \le a + b \le 3 are 1,1,1,2,2,1{1, 1}, {1, 2}, {2, 1}, but in each of these pairs gcd⁡(a,b)\gcd(a, b) equals 11, so there is no answer.

In the third sample test, gcd⁡(14,4)=2\gcd(14, 4) = 2.

在第一个测试用例中,11≤6+9≤1511 \le 6 + 9 \le 15,gcd⁡(6,9)=3\gcd(6, 9) = 3,所有条件均满足。注意,这并非唯一的可能答案,例如 {4,10}\{4, 10\}、{5,10}\{5, 10\}、{6,6}\{6, 6\} 对该测试用例而言也是有效的答案。

在第二个测试用例中,唯一满足条件 1≤a+b≤31 \le a + b \le 3 的数对 {a,b}\{a, b\} 是 {1,1}\{1, 1\}、{1,2}\{1, 2\}、{2,1}\{2, 1\},但这些数对中每一对的 gcd⁡(a,b)\gcd(a, b) 均为 11,因此无解。

在第三个样例测试中,gcd⁡(14,4)=2\gcd(14, 4) = 2。

输入解题思路,AI测评打分。不知道怎么写?

首页