실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
학생들의 스트레스를 풀어주기 위해 선생님은 교실에 거대한 디스코 볼을 설치하고 학생들에게 춤을 가르치려고 합니다!
선생님은 학생들에게 '셔플'을 가르치기로 결정했습니다. 셔플은 ( ) 명의 학생들이 어떤 순서로 한 줄로 선 후 계속해서 '셔플'을 하고, 각각의 셔플마다 학생들의 순서를 재배열하는 것입니다. 학생들이 자신들의 위치를 쉽게 찾을 수 있도록, 선생님은 학생들의 줄을 위치별로 까지 표시해둡니다. 따라서 줄의 처음 학생은 위치 1에, 다음 학생은 위치 2에 있게 되며, 이런 식으로 위치 까지 이어집니다.
셔플은 개의 숫자 으로 설명되며, 위치 에 있는 학생은 셔플 동안 위치 로 이동합니다(따라서, 각 는 범위에 있게 됩니다). 모든 학생은 셔플 동안 새로운 위치로 이동합니다. 불행히도, 모든 가 서로 다른 것은 아니므로, 여러 학생이 셔플 동안 같은 위치로 이동하려고 시도할 수 있고, 이 후에는 남아있는 모든 셔플 동안 함께 움직이게 됩니다.
선생님은 몇몇 위치에는 얼마나 많은 셔플이 이루어지든 상관없이 항상 학생이 위치함을 알아차렸습니다. 몇 개의 위치가 이런 식으로 항상 소를 포함하는지를 세어서 알려 주세요.
첫 번째 입력 줄에는 학생의 수 이 있습니다. 다음 줄에는 개의 정수 이 있습니다.
어떤 셔플이 이루어지든 항상 학생을 포함하게 될 위치의 수를 출력해주세요.
4 3 2 1 3
3
출처: USACO 2017 December Contest, Silver Problem 3. The Bovine Shuffle