Ceremonial Parade
Time limit2sMemory limit256 MB
Build an n by n matrix of primes using exactly k distinct primes so every row product and every column product has the same number of divisors.
- Level
Medium6 of 10
- Topics
- Math, Number theory, Combinatorics, Implementation
- Solved
- No attempts yet
Problem
Gru decided to hold a ceremonial parade. An essential part of the parade is the formation of his mighty army of minions.
The parade takes place on Central Square, which has the shape of a square. The length and width of the square are n meters. It is divided into cells one meter long and one meter wide, so it contains n2 cells. In other words, Central Square is an n × n matrix.
Gru gave each minion in his army a colored shirt with a prime number written on it. Some shirts may have the same number written on them. Now it is up to the minions to line up the way Gru wants. In the formation, exactly one minion occupies each cell of the square. There are also additional requirements for the formation. The first is that the parade must involve minions whose shirts carry exactly k distinct prime numbers. The second requirement is that the product of the numbers on the shirts in each row and in each column must have the same number of divisors. Also note that Gru only has shirts with prime numbers not exceeding 107.
Help construct a formation that satisfies all the requirements, or determine that this is impossible.
Input
The input consists of a single line containing two integers k and n (1 ≤ k ≤ 109, 1 ≤ n ≤ 1000): the number of required distinct prime numbers and the size of the square.
Output
Output an n × n matrix of prime numbers not exceeding 107 that satisfies all the requirements, or −1 if the formation cannot be constructed.