309050: CF1617B. GCD Problem

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

GCD Problem

题意翻译

给定一个正整数 $n$,请找出一组**互不相同**的正整数 $a,b,c$,使得: - $a+b+c=n$。 - $\gcd(a,b)=c$。 其中 $\gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公因数。 数据范围: - $t$ 组数据,$1\leqslant t\leqslant 10^5$。 - $10\leqslant n\leqslant 10^9$。 Translated by Eason_AC 2021.12.17

题目描述

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)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ x $ and $ y $ .

输入输出格式

输入格式


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 $ ).

输出格式


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.

输入输出样例

输入样例 #1

6
18
63
73
91
438
122690412

输出样例 #1

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

说明

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 $ .

Input

题意翻译

给定一个正整数 $n$,请找出一组**互不相同**的正整数 $a,b,c$,使得: - $a+b+c=n$。 - $\gcd(a,b)=c$。 其中 $\gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公因数。 数据范围: - $t$ 组数据,$1\leqslant t\leqslant 10^5$。 - $10\leqslant n\leqslant 10^9$。 Translated by Eason_AC 2021.12.17

加入题单

上一题 下一题 算法标签: