/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 以上 N 以下の整数であって、M で割った余りが R になるものすべてに対する popcount の総和を求めてください。
ただし、正整数 X に対して X の popcount とは X を二進表記したときの 1 の個数、すなわち 2^k の位が 1 となる非負整数 k の個数のことです。
1 つの入力につき、 T 個のテストケースに答えてください。
制約
- 1 \leq T \leq 10^5
- 1 \leq M \leq N \leq 10^9
- 0 \leq R < M
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。入力の 1 行目は以下の通りである。
T
そして、T 個のテストケースが続く。これらはそれぞれ以下の形式で与えられる。
N M R
出力
T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。
入力例 1
2 12 5 1 6 1 0
出力例 1
6 9
1 つ目のテストケースでは、1 の popcount が 1、6 の popcount が 2、11 の popcount が 3 であるため 1+2+3 の計算結果である 6 を出力します。
2 つ目のテストケースでは、1 の popcount が 1、2 の popcount が 1、3 の popcount が 2、4 の popcount が 1、5 の popcount が 2、6 の popcount が 2 であるため 1+1+2+1+2+2 の計算結果である 9 を出力します。
Score : 600 points
Problem Statement
Find the sum of popcounts of all integers between 1 and N, inclusive, such that the remainder when divided by M equals R.
Here, the popcount of a positive integer X is the number of 1s in the binary notation of X, that is, the number of non-negative integers k such that the 2^ks place is 1.
For each input, process T test cases.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq M \leq N \leq 10^9
- 0 \leq R < M
- All values in the input are integers.
Input
The input is given from Standard Input in the following format. The first line is as follows:
T
T test cases follow. Each of them is given in the following format:
N M R
Output
Print T lines. The i-th line should contain the answer to the i-th test case.
Sample Input 1
2 12 5 1 6 1 0
Sample Output 1
6 9
In the 1-st test case, the popcount of 1 is 1, the popcount of 6 is 2, and the popcount of 11 is 3, so 1+2+3=6 should be printed.
In the 2-nd test case, the popcount of 1 is 1, 2 is 1, 3 is 2, 4 is 1, 5 is 2, and 6 is 2, so 1+1+2+1+2+2=9 should be printed.