GCD vs LCM solution codechef

GCD vs LCM solution codechef

You are given a positive integer nn. You have to find 44 positive integers a,b,c,da,b,c,d such that
  • a+b+c+d=na+b+c+d=n, and
  • gcd(a,b)=lcm(c,d)gcd(a,b)=lcm⁡(c,d).
If there are several possible answers you can output any of them. It is possible to show that the answer always exists. In this problem gcd(a,b)gcd(a,b) denotes the greatest common divisor of aa and bb, and lcm(c,d)lcm⁡(c,d) denotes the least common multiple of cc and dd.
Input
The input consists of multiple test cases. The first line contains a single integer tt (1t1041≤t≤104) — the number of test cases. Description of the test cases follows. Each test case contains a single line with integer nn (4n1094≤n≤109) — the sum of aabbcc, and dd.
Output
For each test case output 44 positive integers aabbccdd such that a+b+c+d=na+b+c+d=n and gcd(a,b)=lcm(c,d)gcd(a,b)=lcm⁡(c,d).
Example
input
Copy
5
4
7
8
9
10
output
Copy
1 1 1 1
2 2 2 1
2 2 2 2
2 4 2 1
3 5 1 1
Note
In the first test case gcd(1,1)=lcm(1,1)=1gcd(1,1)=lcm⁡(1,1)=11+1+1+1=41+1+1+1=4. In the second test case gcd(2,2)=lcm(2,1)=2gcd(2,2)=lcm⁡(2,1)=22+2+2+1=72+2+2+1=7. In the third test case gcd(2,2)=lcm(2,2)=2gcd(2,2)=lcm⁡(2,2)=22+2+2+2=82+2+2+2=8. In the fourth test case gcd(2,4)=lcm(2,1)=2gcd(2,4)=lcm⁡(2,1)=22+4+2+1=92+4+2+1=9. In the fifth test case gcd(3,5)=lcm(1,1)=1gcd(3,5)=lcm⁡(1,1)=13+5+1+1=103+5+1+1=10.

Leave a Comment