HDU 6121 Build a tree

/ 0评 / 0

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

Problem Description

HazelFan wants to build a rooted tree. The tree has $ n$ nodes labeled $ 0$ to $ n−1$, and the father of the node labeled $ i$ is the node labeled$ \lfloor\frac{i-1}{k}\rfloor$. HazelFan wonders the size of every subtree, and you just need to tell him the $ XOR$ value of these answers.

Input

The first line contains a positive integer $ T(1≤T≤5)$, denoting the number of test cases.
For each test case:
A single line contains two positive integers $ n,k(1≤n,k≤1018)$.

Output

For each test case:
A single line contains a nonnegative integer, denoting the answer.

Sample Input

Sample Output

Source

2017 Multi-University Training Contest - Team 7

题解:

赛后发现非常可写。只是我不知道从1开始异或的规律(逃)。
从一开始连续异或到 n 的连续XOR值
if n % 4==1 XOR= 1
if n % 4==2 XOR= n+1
if n % 4==3 XOR= 0
if n % 4==0 XOR= n

Code

发表评论

电子邮件地址不会被公开。 必填项已用*标注