Bits and Gahui
Time limit0.5sMemory limit256 MB
Count multiples of A up to B whose binary representation has 1s in all N specified bit positions.
- Level
Medium7 of 10
- Topics
- Bit manipulation, Dynamic programming, Math, Combinatorics
- Solved
- No attempts yet
Problem
You are given N conditions of the following form.
- The i-th bit must be 1. That is, for any number X, the value of X & (1 << i) must not be 0.
Write a program that counts how many multiples of A among the integers from 1 to B satisfy all of these conditions.
Input
The first line gives N (0 ≤ N < 32), A, and B (0 < A, B < 2^31), separated by spaces.
Each of the next N lines gives one bit that must be set. These values are non-negative integers at most 30, and no bit is repeated.
Output
Print the number of multiples of A among the integers from 1 to B that satisfy the given N conditions.