# HDU 6121 Build a tree （技巧）

## 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≤10^{18})$ .

## Output

For each test case:

A single line contains a nonnegative integer, denoting the answer.

2
5 2
5 3

7
6

## 思路

• $cnt[i]$ ，第 $i$ 层的节点个数
• $sum[i]$ ，高为 $i$ 的满 $k$ 叉树节点个数
• $xor[i]$ ，高为 $i$ 的满 $k$ 叉树所有子树异或和

## AC 代码

#include<bits/stdc++.h>
typedef __int64 LL;
using namespace std;
const int maxn =105;
LL cnt[maxn];       // 第 i 层的节点个数
LL sum[maxn];       // 高为 i 的满 k 叉树节点个数
LL xxor[maxn];      // 高为 i 的满 k 叉树所有子树异或和
LL n,k;

inline LL F(LL a,LL b)
{
return b&1?a:0;
}

{
if(dep==0)return 0;
}

LL solve()
{
if(k==1)        // 对 1 特判
{
int mo = n%4;
if(mo==0)
return n;
else if(mo==1)
return 1;
else if(mo==2)
return n+1;
else
return 0;
}
int dep=1;
sum[dep]=cnt[dep]=xxor[dep]=1;
while((n-sum[dep])/k>=cnt[dep])     // 枚举深度（所有满节点的层）
{
dep++;
cnt[dep] = cnt[dep-1]*k;
sum[dep] = sum[dep-1] + cnt[dep];
xxor[dep] = sum[dep]^F(xxor[dep-1],k);
}
return dfs(dep,n-sum[dep]);
}

int main()
{
int T;
cin>>T;
while(T--)
{
LL ans;
cin>>n>>k;
ans=solve();
cout<<ans<<endl;
}
return 0;
}