Non-coprime Split (Codeforces 1872C)
Tags: Math, number theory

You are given two integers $$$l \le r$$$. You need to find positive integers $$$a$$$ and $$$b$$$ such that the following conditions are simultaneously satisfied: $$$l \le a + b \le r$$$ $$$\gcd(a, b) \neq 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$$$.

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \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 $$$2$$$ integers $$$l, r$$$ ($$$1 \le l \le r \le 10^7$$$).

Output: 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.

Note: In the first test case, $$$11 \le 6 + 9 \le 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 \le a + b \le 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$$$.

Sample Inputs:
11
11 15
1 3
18 19
41 43
777 777
8000000 10000000
2000 2023
1791791 1791791
1 4
2 3
9840769 9840769

Sample Outputs:
6 9
-1
14 4
36 6
111 666
4000000 5000000 
2009 7
-1
2 2
-1
6274 9834495

Solution (Python):
def solve(l, r):
    if l < r or r % 2 == 0:
        r2 = r - r % 2
        (a, b) = (2, r2 - 2)
        if b > 1:
            return (a, b)
        return -1
    q = int(r ** 0.5)
    for d in range(3, q + 1, 2):
        if r % d == 0:
            return (d, r - d)
    return -1
for _ in range(int(input())):
    (l, r) = map(int, input().split())
    s = solve(l, r)
    if s == -1:
        print(-1)
    else:
        print(s[0], s[1])

Solution (Python):
def primes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]
pr = primes(3162)[1:]
for _ in range(int(input())):
    (l, r) = map(int, input().split())
    if r < 4:
        print(-1)
    elif r > l:
        print(r // 2, r // 2)
    elif r % 2 == 0:
        print(r // 2, r // 2)
    elif r in pr:
        print(-1)
    else:
        for p in pr:
            if r % p == 0:
                s = r // p
                print(2 * s, (p - 2) * s)
                break
        else:
            print(-1)

Solution (Python):
from math import ceil

def isprime(n):
    v = -1
    if n <= 1:
        return [False, v]
    if n == 2 or n == 3:
        return [True, v]
    if n % 2 == 0 or n % 3 == 0:
        v = 3
        return [False, v]
    for i in range(5, int(pow(n, 0.5)) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            if n % i == 0:
                v = i
            else:
                v = i + 2
            return [False, v]
    return [True, v]
for _ in range(int(input())):
    (l, r) = map(int, input().split())
    if r - l >= 1:
        if r // 2 == 1:
            print(-1)
        else:
            print(r // 2, r // 2)
    elif l % 2 == 0:
        if l == 2:
            print(-1)
        else:
            print(l // 2, l // 2)
    else:
        ans = isprime(l)
        if ans[0] or ans[1] == -1:
            print(-1)
        else:
            print(ans[1], l - ans[-1])