分数: 600 点
问题陈述
求 之间所有整数的 popcount 总和 1 和 N,包含在内,这样除以时的余数 M 等于 R.
这里,popcount为正整数 X 是数量 1s 的二进制表示法 X,即非负整数的个数 k 这样 2^k的位置是 1.
对于每个输入,处理 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-st 测试用例,popcount 1 is 1,popcount 6 is 2,以及 popcount
应打印 11 is 3,所以 1+2+3=6 。
在 2-nd 测试用例,popcount 1 is 1, 2 is 1, 3 is 2, 4 is 1, 5 is 2,和 6 is 2,所以 1+1+2+1+2+2=9 。