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(a1,a2)=gcd(1,140)=1
gcd(a3,a4)=gcd(4,70)=2
gcd(a5,a6,a7)=gcd(30,105,42)=3
gcd(a2,a3)=gcd(140,4)=4
gcd(a2,a4,a5,a6)=gcd(140,70,30,105)=5
gcd(a5,a7)=gcd(30,42)=6
gcd(a2,a4,a6,a7)=gcd(140,70,105,42)=7
Name |
---|