問題一覧 > 通常問題

No.3444 Interval Xor MST

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 14
作問者 : 👑 potato167 / テスター : noya2
お気に入りにしたユーザー ProblemId : 12989 / 自分の提出
問題文最終更新日: 2026-02-06 02:33:37
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 492 (順位表) の他の問題:

Problem Statement

You are given a positive integer $N$ and a non-negative integer $M$.

The vertices of a weighted complete graph $G$ with $N$ vertices are numbered from $0$ to $N - 1$, and for any $0 \leq a < b < N$, the weight of the edge connecting vertex $a$ and vertex $b$ is $(a + M) \oplus (b + M)$. Here, $\oplus$ denotes the bitwise exclusive OR.

Find the sum of the edge weights of a minimum spanning tree of $G$.

You are given $T$ test cases; solve each of them.

Constraints

  • $1\leq T\leq 10^{5}$
  • $1\leq N\leq 2\times 10^{9}$
  • $0\leq M\leq 2\times 10^{9}$
  • All input values are integers.

Input

The input is given from Standard Input in the following format.

$T$
$case_{1}$
$case_{2}$
$\vdots$
$case_{T}$

Each case is given in the following format.

$N$ $M$

Output

Output $T$ lines.

On the $i$-th line, output the answer for $case_{i}$.

Sample

Sample 1
Input
3
3 2
167 924
1234567890 1234567890
Output
7
2551
21772702017

For the $1$st test case, the following holds for the edge weights.

  • The weight of the edge connecting vertex $0$ and vertex $1$ is $(0 + 2)\oplus(1 + 2)=1$.
  • The weight of the edge connecting vertex $0$ and vertex $2$ is $(0 + 2)\oplus(2 + 2)=6$.
  • The weight of the edge connecting vertex $1$ and vertex $2$ is $(1 + 2)\oplus(2 + 2)=7$.

Therefore, the minimum spanning tree consists of $2$ edges: the edge connecting vertex $0$ and vertex $1$, and the edge connecting vertex $0$ and vertex $2$.

On the $1$st line, output the sum of these edge weights, $1 + 6 = 7$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。