GCD Problem (Codeforces 1617B)
Tags: Math, number theory

Given a positive integer $$$n$$$. Find three distinct positive integers $$$a$$$, $$$b$$$, $$$c$$$ such that $$$a + b + c = n$$$ and $$$\operatorname{gcd}(a, b) = c$$$, where $$$\operatorname{gcd}(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Input: The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Description of the test cases follows.The first and only line of each test case contains a single integer $$$n$$$ ($$$10 \le n \le 10^9$$$).

Output: For each test case, output three distinct positive integers $$$a$$$, $$$b$$$, $$$c$$$ satisfying the requirements. If there are multiple solutions, you can print any. We can show that an answer always exists.

Note: In the first test case, $$$6 + 9 + 3 = 18$$$ and $$$\operatorname{gcd}(6, 9) = 3$$$.In the second test case, $$$21 + 39 + 3 = 63$$$ and $$$\operatorname{gcd}(21, 39) = 3$$$.In the third test case, $$$29 + 43 + 1 = 73$$$ and $$$\operatorname{gcd}(29, 43) = 1$$$.

Sample Inputs:
6
18
63
73
91
438
122690412

Sample Outputs:
6 9 3
21 39 3
29 43 1
49 35 7
146 219 73
28622 122661788 2

Solution (Python):
from sys import stdin, stdout
t = int(stdin.readline())
for i in range(t):
    n = int(stdin.readline())
    if n % 2 == 0:
        a = 2
    else:
        a = (n - n % 4) // 2 - 1
    b = n - a - 1
    stdout.write(str(a) + ' ' + str(b) + ' 1\n')

Solution (Python):
for n in [*map(int, open(0))][1:]:
    print((m := (2, n // 4 * 2 - 1)[n % 2]), n - m - 1, 1)

Solution (Python):
for n in [*map(int, open(0))][1:]:
    print((m := (2, n // 4 * 2 - 1)[n % 2]), n - m - 1, 1)