1787A - Exponential Equation - 800

1787A - Exponential Equation (constructive algorithms, math, 800)

Logic

The equation is a mix of multiplication and exponential operations. Given the nature of exponential operations, $𝑥^𝑦$ and $𝑦^𝑥$ can grow very large very quickly as x and y increase.

We can try to simplify the equation.

If we can somehow set one of the variables x or y to 1, the equation simplifies.

This is because any number (except zero) raised to the power of 1 is the number itself, and any number raised to the power of 0 is 1.

So, if we set x = 1, the equation simplifies to 1^y * y + y^1 * 1 = n, which further simplifies to y + y = n, or 2y = n. This is a simple linear equation, and we can see that for any even n greater than 2, it has a solution in integers. The solution is x = 1 and y = n/2.

• For n = 2, we can set both x and y to 1, and the equation holds. It can be a base case.
• For odd n greater than 2, and for n = 1, there’s no solution in integers.

Solution

def solve():
    n = int(input())
    if n == 2:
        print(1, 1)
    elif n % 2 == 0:
        print(1, n//2)
    else:
        print(-1)


for _ in range(int(input())):
    solve()