# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* utkarsh_25dec

*tabr*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

1569

# PREREQUISITES:

None

# PROBLEM:

Given 1 \leq X\leq 10^{12}, find whether there exist integers 1 \leq A, B, C \leq 10^6 such that AB + C = X.

# EXPLANATION:

If X = 1, no solution exists because AB+C \geq 2 for any choice of A, B, C.

Otherwise, a solution always exists!

There are many different approaches, Iâ€™ll elaborate on one of them.

Notice that X = AB+C is vaguely reminiscent of division.

In particular, if we fix the value of B, Euclidâ€™s division lemma tells us that there exist unique integers q (the quotient) and r (the remainder) such that:

- X = qB + r
- 0 \leq r \lt B

If weâ€™re able to choose B appropriately such that 1 \leq q, r \leq 10^6, weâ€™ll be done, since we can directly take A = q and C = r.

In fact, we donâ€™t really need to worry much about r. Since r \lt B, itâ€™ll never exceed 10^6 anyway, as long as we choose B \leq 10^6.

So, our aim is to keep q small enough.

This can be achieved by picking a large enough B.

For example, suppose we pick B = 10^6 and then find q and r.

Then, since X \leq 10^{12}, weâ€™ll surely have q \leq 10^6, which takes care of all the upper bounds.

This solves the problem for almost all cases â€” the only ones it doesnâ€™t solve are the ones for which q = 0 or r = 0.

Letâ€™s see how we can fix those.

- If q = 0, that would mean X \lt 10^6.

Solving such a case is quite easy though, since we have several options.

For example, you can choose A = B = 1 and C = X-1, or A = C = 1, B = X-1. - If r = 0, that would mean X is a multiple of 10^6.

In such a case, we can decrease q by 1 and set r = 10^6.

This will fail only for X = 10^6, since decreasing q by 1 will make it 0.

However, X = 10^6 can be solved using the previous case anyway, so thereâ€™s no issue.

Putting it all together,

- If X = 1, no solution exists.
- If X \leq 10^6, choose A = B = 1, C = X-1 (or similar).
- If X \gt 10^6, find q and r, the quotient and remainder when X is divided by 10^6. Then,
- If r \gt 0, choose A = q, B = 10^6, C = r
- If r = 0, choose A = q-1, B = 10^6, C = 10^6

# TIME COMPLEXITY

\mathcal{O}(1) per test case.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
x = int(input())
if x == 1: print(-1)
elif x <= 1000001: print(1, 1, x-1)
else:
m = 10**6
if x%m == 0: print(m, x//m - 1, m)
else: print(m, x//m, x % m)```
```