빛의 도시
면접 대비시간 제한1초메모리 제한512 MB
처음에 모두 켜져 있는 N개의 전등이 있고, i를 받으면 i의 배수 위치 전등을 모두 뒤집는 조작을 k번 한다. 이 과정에서 동시에 꺼져 있는 전등 개수의 최댓값을 구한다.
문제
파리는 17세기부터 "ville lumière"(빛의 도시)라고 불려 왔다. 이 별명을 얻은 데에는 기념비, 조각상, 교회, 분수 같은 유명한 장소를 비추는 수많은 도시 조명도 한몫했다.
파리의 이 공공 조명에는 1번부터 N번까지 번호가 붙어 있고, 처음에는 모두 켜져 있다. 한 해커 집단이 조명을 묶음 단위로 반전시킬 수 있는 방법을 알아냈다. 해커들이 프로그램을 실행할 때마다, 자신들이 제어할 수 없는 수 i가 도시 조명을 관리하는 시스템으로 전달된다. 그러면 번호가 i, 2i, 3i, ... (N 이하)인 조명의 상태가 즉시 바뀐다. 켜져 있던 조명은 꺼지고, 꺼져 있던 조명은 켜진다.
밤 동안 해커들은 프로그램을 k번 실행한다. 어느 순간에든 동시에 꺼져 있는 조명의 개수로 가능한 최댓값은 얼마인가?
입력
입력은 여러 줄로 이루어지며, 각 줄에는 정수 하나가 들어 있다.
- 첫째 줄에는 조명의 개수 N이 들어 있다.
- 둘째 줄에는 해커가 프로그램을 실행하는 횟수 k가 들어 있다.
- 다음 k개 줄에는 조명을 관리하는 시스템으로 전달되는 수 i가 들어 있다.
출력
출력은 한 줄이며, 그 내용은 어느 순간에든 동시에 꺼져 있는 조명의 개수로 가능한 최댓값인 정수 하나이다.
제한
- 1 ≤ N ≤ 1 000 000;
- 1 ≤ k ≤ 100;
- 1 ≤ i ≤ N.