27428번 - Light 다국어

In the physics laboratory there are N light bulbs in a row, numbered from 1 to N. Initially, all the bulbs are turned off. During class, each of the K students chooses an integer positive number d_i (2 ≤ d_i ≤ N), and changes the state of all the bulbs whose number is divisible by di . Changing the state of a bulb means that if the bulb is turned on, then it will become turned off, and if it is turned off, it will become turned on. After changing the state of the bulbs, the student leaves the class.

Write a program that computes how many light bulbs will remain turned on, after all the students leave the class.

The standard input contains on the first line the positive integer N, representing the number of the light bulbs. The second line contains the number K, the number of students. The third line contains K integers d₁, d₂, ..., d_K, separated by a single white space.

Your program should write to the standard output a single line containing the number of the bulbs that will remain turned on, after all the students leave the class.

• 3 ≤ N ≤ 10¹²
• 1 ≤ K ≤ 22
• 1 ≤ d_i ≤ min(N, 10⁶)
• The numbers d_i are not necessarily distinct

Initially, all the bulbs are turned off. After the first student changes the state of the bulbs, the 2^nd, 4^th, 6^th and the 8^th bulb will be on. After the second student changes the state of the bulbs, the 2^nd, 3^rd, 4^th and the 8^th bulb will remain on.