[Solution] Ela and Prime GCD solution codeforces

Ela and Prime GCD solution codeforces – After a long, tough, but fruitful day at DTL, Ela goes home happily. She entertains herself by solving Competitive Programming problems. She prefers short statements, because she already read too many long papers and documentation at work. The problem of the day reads:

Table of Contents

[Solution] Ela and Prime GCD solution codeforces

You are given an integer 𝑐c. Suppose that 𝑐c has 𝑛n divisors. You have to find a sequence with 𝑛1n−1 integers [𝑎1,𝑎2,...𝑎𝑛1][a1,a2,…an−1], which satisfies the following conditions:

  • Each element is strictly greater than 11.
  • Each element is a divisor of 𝑐c.
  • All elements are distinct.
  • For all 1𝑖<𝑛11≤i<n−1gcd(𝑎𝑖,𝑎𝑖+1)gcd(ai,ai+1) is a prime number.

In this problem, because 𝑐c can be too big, the result of prime factorization of 𝑐c is given instead. Note that gcd(𝑥,𝑦)gcd(x,y) denotes the greatest common divisor (GCD) of integers 𝑥x and 𝑦y and a prime number is a positive integer which has exactly 22 divisors.

[Solution] Ela and Prime GCD solution codeforces

The first line contains one integer 𝑡t (1𝑡1041≤t≤104) – the number of test cases.

The first line of each test case contains one integer 𝑚m (1𝑚161≤m≤16) – the number of prime factor of 𝑐c.

The second line of each test case contains 𝑚m integers 𝑏1,𝑏2,,𝑏𝑚b1,b2,…,bm (1𝑏𝑖<2201≤bi<220) — exponents of corresponding prime factors of 𝑐c, so that 𝑐=𝑝𝑏11𝑝𝑏22𝑝𝑏𝑚𝑚c=p1b1⋅p2b2⋅…⋅pmbm and 𝑛=(𝑏1+1)(𝑏2+1)(𝑏𝑚+1)n=(b1+1)(b2+1)…(bm+1) hold. 𝑝𝑖pi is the 𝑖i-th smallest prime number.

It is guaranteed that the sum of 𝑛𝑚n⋅m over all test cases does not exceed 220220.

Output

Print the answer for each test case, one per line. If there is no sequence for the given 𝑐c, print 1−1.

Otherwise, print 𝑛1n−1 lines. In 𝑖i-th line, print 𝑚m space-separated integers. The 𝑗j-th integer of 𝑖i-th line is equal to the exponent of 𝑗j-th prime number from 𝑎𝑖ai.

If there are multiple answers, print any of them.

[Solution] Ela and Prime GCD solution codeforces

input

Copy
5
2
1 1
1
1
3
1 1 1
1
4
2
2 1

output

Copy
0 1 
1 1 
1 0 
1 
0 1 1 
0 0 1 
1 0 1 
1 1 0 
0 1 0 
1 1 1 
1 0 0 
-1
2 0 
1 1 
0 1 
2 1 
1 0 

[Solution] Ela and Prime GCD solution codeforces

In each test case, the values of 𝑐c are 662230301616, and 1212 in that order.

In the first test case, 11223366 are divisors of 66. Here, sequences [2,6,3][2,6,3] and [3,6,2][3,6,2] can be answer. Permutation [3,2,6][3,2,6] is invalid because gcd(𝑎1,𝑎2)=1gcd(a1,a2)=1 is not a prime number.

In the forth test case, 112244881616 are divisors of 1616. Among the permutation of sequence [2,4,8,16][2,4,8,16], no valid answer exist.

For Solution

“Click Here”

Leave a Comment