cho.shCount the Bits
2^b 미만의 k의 배수들을 이진수로 썼을 때 1의 개수를 모두 더해 10^9+9로 나눈 나머지를 구한다.
어려움8동적 계획법수학조합론아직 제출이 없습니다시간 제한2초메모리 제한512 MB문제
Given a value k and a number of bits b, calculate the total number of 1-bits in the binary representations of all multiples of k that are between 0 and 2b-1 (inclusive).
입력
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs.
Each test case will consist of a single line containing two space-separated integers k (1 ≤ k ≤ 1,000) and b (1 ≤ b ≤ 128), where k and b are as described above.
출력
Output a single integer, which is the total number of 1-bits in the binary representations of all multiples of k that are between 0 and 2b-1 (inclusive). Since this number may be very large, output it modulo 109+9.
힌트
Consider the second sample: k=10 and b=5.
25-1 = 31. All the multiples of 10 between 0 and 31 are: 10, 20 and 30.
- 10 = 01010b (2 1-bits)
- 20 = 10100b (2 1-bits)
- 30 = 11110b (4 1-bits)
That’s a total of 2+2+4=8 1-bits.