비트와 가희
시간 제한0.5초메모리 제한256 MB
1부터 B까지의 A의 배수 가운데 지정된 N개 비트가 모두 1인 수의 개수를 센다.
문제
다음과 같은 조건이 N개 주어진다.
- i번째 bit가 1이어야 한다. 즉, 어떤 수 X가 있다면 X & (1 << i)의 값이 0이 아니어야 한다.
1 이상 B 이하의 정수 중 이러한 조건을 모두 만족하는 A의 배수는 몇 개인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(0 ≤ N < 32), A, B(0 < A, B < 2^31)가 공백으로 구분되어 주어진다.
둘째 줄부터 N개의 각 줄에는 켜져야 하는 bit가 N개 주어진다. 이 값들은 30 이하인 음이 아닌 정수이며, 켜져야 하는 bit는 중복으로 주어지지 않는 것이 보장된다.
출력
1 이상 B 이하의 정수 중 주어진 N개의 조건들을 만족하는 A의 배수의 개수를 출력하라.