Solution for problem Tygyn
The solution is based on a special and innovative tree that contains all natural numbers. We will call this special tree the Divisor Tree. The root of the tree is vertex number 1. Each number greater than 1 can be written as a product of prime numbers. The father of any vertex is the number equal to the number divided by the largest prime number dividing it. For example, 3 * 5 * 5 * 7 has 3 * 5 * 5 as father, while 2 * 2 * 2 has 2 * 2 as father.
In order to understand its structure, you can have a look on the image to the right. Here you can find a descriptive part of the Divisor Tree. Note that all prime numbers share an edge with root number 1, and the height of each vertex is equal to the number of times you should divide it by a prime number in order to make the number equal to 1 (the sum of exponents of the prime numbers in its factorisation).
If we have a look at the Divisor Tree, at its properties and structure, in relationship with the task statement, we will see that one can make a herd of all the cows whose numbers are in a subtree of an existing cow. Minimizing the number of herds means creating a heard for each cow, except for the ones who have an ancestor in the tree. If the cow has an ancestor in the tree, it means it can go in the herd whose representant (the minimum number in the herd) is the existing ancestor. This way, both the correctness of the herds and their minimality are respected.
There are many ways to implement the algorithm. We must somehow search the tree, so we must keep the highest prime divisor for any number as we visit all vertices. The official implementation uses BFS on the Divisor Tree, marking as it goes the herd each vertex belongs to. The input is easily treated with a bool array marking all given cows.
The solution also requires some knowledge of the prime numbers up to M. We can use the sieve of Eratosthenes to find them, or the linear sieve for finding all primes up to some number. The final complexity is O(N + M * \log(\log M)) or O(N + M), depending on how the sieve is implemented.
Request Notice
Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana. Multumim lui 
