luogu#P11036. 【MX-X3-T3】「RiOI-4」GCD 与 LCM 问题

【MX-X3-T3】「RiOI-4」GCD 与 LCM 问题

题目背景

「既然你说你不了解她,为什么又可以断言她一定是因为……」

是呀,自己对零羽还了解的确实不够多……泠珞这样想着。

在残缺的记忆当中,她只能想起,她和零羽的最大公约数,就是「音乐」。

还缺了什么呢?泠珞不知道。她只知道,那所缺失的,和「音乐」加起来,就是她的一切。一切的总和。

滴答,滴答。叮咚,叮咚。如果把长短不一、断断续续的钢琴声拼接在一起,能够回忆起什么吗。

题目描述

给定一个正整数 aa,请你构造三个正整数 b,c,db,c,d 使得 a+b+c+d=gcd(a,b)+lcm(c,d)a+b+c+d=\gcd(a,b)+\operatorname{lcm}(c,d)。一个测试点内有多组数据。

由于出题人想把自己 QQ 号写题目里,你需要保证 b,c,d1634826193b,c,d\le 1\,634\,826\,193

如有多种可能的答案,输出任意一个均可。

输入格式

第一行一个正整数 tt 表示数据组数。

接下来 tt 行每行一个正整数 aa

输出格式

输出 tt 行,每行三个正整数 b,c,db,c,d

如有多种可能的答案,输出任意一个均可。

4
1
2
3
20120712
7 9 2
9 6 8
5 9 2
8065343 8750 6446

提示

【样例解释】

样例的构造为:

1+7+9+2=19=gcd(1,7)+lcm(9,2)1+7+9+2=19=\gcd(1,7)+\operatorname{lcm}(9,2)
2+9+6+8=25=gcd(2,9)+lcm(6,8)2+9+6+8=25=\gcd(2,9)+\operatorname{lcm}(6,8)
3+5+9+2=19=gcd(3,5)+lcm(9,2)3+5+9+2=19=\gcd(3,5)+\operatorname{lcm}(9,2)
$20\,120\,712+8\,065\,343+8\,750+6\,446=28\,201\,251=\gcd(20\,120\,712,8\,065\,343)+\operatorname{lcm}(8\,750,6\,446)$

容易验证均满足要求。

【数据范围】

测试点 分数 tt\le aa\le 特殊性质
11 22 1010
22 55 5050
33 1717 10610^6 5×1085\times10^8
44 2929 109110^9-1 aa 为奇数
55 4747 2×1062\times10^6 10910^9

对于 100%100\% 的数据,1t2×1061\le t\le2\times10^61a1091\le a\le 10^9