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 ⌊i−1k⌋. 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).
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.
A single line contains a nonnegative integer, denoting the answer.
Sample Input
2
5 2
5 3
Sample Output
7
6
题意：有一颗树，节点编号0~n-1 ，节点 i 的父亲节点编号 ⌊i−1k⌋ ，求所有子树大小相异或值？
思路：可以发现这是一棵完全 k 叉树 ，那么所有叶子节点高度差最多为1，且所有最高层叶子都靠左。那么我们从上向下找最高最靠右的叶子，然后回溯时计算：这时当前节点子树的大小特殊，其左边的所有同层次节点子树大小相同，其右边的所有同层次节点子树大小相同，所以对于每一层只需要考虑三种不同的节点子树。
官方题解：
代码如下：(唉，比赛时代码没调出来，赛后才调完，有点可惜~)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const LL N=1e18+;
LL cnt[];
LL pw[];
LL n,k,m;
int deep;
LL ans=;
LL L,R,mid; void dfs(int x)
{
if(x>deep) return ;
dfs(x+);
LL pos=(cnt[x]-)%k; ///left brother; int f=(cnt[x]-)&;
if(f) ans^=L; LL cR=pw[x]-cnt[x];
f=cR&;
if(f) ans^=R; ans^=mid; mid=pos*L+mid++(k-pos-)*R;
L=L*k+;
R=R*k+;
} int main()
{
int T; cin>>T;
while(T--)
{
scanf("%lld%lld",&n,&k);
if(k == ){
if(n% == ) ans = n;
else if(n% == ) ans = ;
else if(n% == ) ans = n+;
else if(n% == ) ans = ;
printf("%lld\n",ans);
continue;
}
LL tmp=;
m=n-; pw[]=;
for(int i=;i<;i++)
{
tmp=tmp*k; pw[i]=tmp;
if(m<tmp || tmp< ) { pw[i]=N; deep=i; break; }
m-=tmp;
}
cnt[deep]=m;
if(m==) { deep--; cnt[deep]=pw[deep]; m=cnt[deep]; }
for(int i=deep-;i>=;i--)
{
cnt[i]=(m+k-)/k;
m=cnt[i];
}
L=; mid=; R=;
ans=;
dfs();
printf("%lld\n",ans);
}
return ;
}