Codeforces Round 931 (Div. 2) |
---|
Finished |
Given an integer n, you construct an array a of n integers, where ai=i for all integers i in the range [1,n]. An operation on this array is defined as follows:
After all the operations ai≤1018 should hold for all 1≤i≤n.
We can show that an answer always exists.
The first line contains one integer t (1≤t≤102) — the number of test cases. The description of the test cases follows.
The first and only line of each test case contains an integer n (3≤n≤3⋅104) — the length of the array.
It is guaranteed that the sum of n over all test cases does not exceed 3⋅104.
The first line should contain an integer k (0≤k≤⌊n6⌋+5) — where k is the number of operations.
The next k lines should contain the description of each operation i.e. 3 integers i, j and k, where 1≤i,j,k≤n and all must be distinct.
3347
1 1 2 3 1 1 3 4 3 3 5 7 5 6 7 2 3 4
In the third test case, a=[1,2,3,4,5,6,7].
First operation:
i=3, j=5, k=7
x=3, y=5, z=7.
a=[1,2,lcm(y,z),4,lcm(x,z),6,lcm(x,y)] = [1,2,35,4,21,6,15].
Second operation:
i=5, j=6, k=7
x=21, y=6, z=15.
a=[1,2,35,4,lcm(y,z),lcm(x,z),lcm(x,y)] = [1,2,35,4,30,105,42].
Third operation:
i=2, j=3, k=4
x=2, y=35, z=4.
a=[1,lcm(y,z),lcm(x,z),lcm(x,y),30,105,42] = [1,140,4,70,30,105,42].
Subsequences whose GCD equal to i is as follows:
gcd
\gcd(a_3, a_4) = \gcd(4, 70) = 2
\gcd(a_5, a_6, a_7) = \gcd(30, 105, 42) = 3
\gcd(a_2, a_3) = \gcd(140, 4) = 4
\gcd(a_2, a_4, a_5, a_6) = \gcd(140, 70, 30, 105) = 5
\gcd(a_5, a_7) = \gcd(30, 42) = 6
\gcd(a_2, a_4, a_6, a_7) = \gcd(140, 70, 105, 42) = 7
Name |
---|