← 返回题目列表

AtCoder · abc283_h

Ex. 人口总数

中文机器翻译题面 查看原题

分数: 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 。