102837: [Atcoder]ABC283 Ex - Popcount Sum

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 $1$s in the binary notation of $X$, that is, the number of non-negative integers $k$ such that the $2^k$s 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.

问题描述

求所有在1和N之间的整数的 popcount 之和，其中这些整数除以M的余数等于R。

这里，正整数X的popcount是X的二进制表示中1的个数，即X的2^k位为1的非负整数k的个数。对于每个输入，处理T个测试用例。

约束

• $1 \leq T \leq 10^5$
• $1 \leq M \leq N \leq 10^9$
• $0 \leq R < M$
• 输入中的所有值都是整数。

输入

输入从标准输入中给出，如下所示。 第一行如下：

$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$。