Fişierul intrare/ieş, tygyn.outSursăTuymaada 2019
AutorAlexandru PetrescuAdăugată dealexpetrescuPetrescu Alexandru alexpetrescu
Timp execuţie pe test0.7 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici


One of Marcel's ancestors, called Manchaary, son of Nyurgun and Sahayaana, was one of the servants of Tygyn Darkhan, at the beginning of the 17th century. Tygyn Darkhan, the great leader who unified the Yakutian tribes, seems to have been very passionate about Number Theory.

One day, he assigned some distinct integers from 2 to M to his N cows. He decided to group the cows, based on their numbers, into as few herds as possible. However, he set the following conditions that should be met for all herds:

  • Let x be the smallest number assigned to the cows in the herd. Each other number of a cow in the herd is of the form x * k, with k integer.
  • All divisors of k (apart from 1) are greater than or equal to any prime divisor of x, for all cows in the herd.

However, Tygyn is a bit busy with keeping peace in his territory, so he asked Manchaary to take care of the cows. The task was rather difficult for Manchaary, but the reward was magnificent: he could then marry beautiful Sardaana!

We know the end of the story: Manchaary solved the task and Sardaana became an ancestor of Marcel. However, when Marcel learned about the story, he thought the task can go back to the lands it originated. That is why the participants in Tuymaada 2019 have to solve it!


Input file contains on the first line the integer numbers N and M. The next line contains N numbers with values between 2 and M, representing the distinct numbers assigned to the N cows of Tygyn Darkhan.


Output file tygyn.out contains the minimal number of herds Manchaary could group the cows into.


  • 1 ≤ N < M ≤ 1.000.000
  • For 10 points, M ≤ 20
  • For 40 points, N ≤ 1.000
  • Note that the scoring is not the same as the one in the official onsite contest


5 100
2 3 11 22 12
10 20
8 12 20 6 3 7 11 13 19 15


You can see a O(N + M) solution description in problem's editorial


Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?