题目链接

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).

Output

For each test case:

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

Sample Input

2

5 2

5 3

Sample Output

7

6

题意：

有一个由n个节点（编号为0~n-1）构成的完全k次树，节点i的父节点的编号为 ⌊(i−1)/k⌋。求出所有的节点大小的异或值。

分析：

因为这是一棵完全k次树，我们手下可以确定的一点就是如果这是一棵满k次树，那么所有的叶子节点都在最后一层，否则除最后一层不满外，倒数第二成还有一部分的叶子结点，也就是说所有叶子结点的高度差最多为1，而且最后一层的叶子结点还全部在左边，倒数第二成的叶子结点全部在右边.

还可以发现或许会存在（如果存在的话仅有一个）有一个节点有子节点，但是子节点的个数又不是k，我们称这个节点为残缺节点。

最后一层的残缺节点肯定就是最后一个节点，我们可以发现该层上它左边节点的大小全部为1，右边全部为0，在往上递归回溯的时候，这时当前节点子树的大小特殊，其左边的所有同层次节点子树大小相同，其右边的所有同层次节点子树大小相同，所以对于每一层只需要考虑三种不同的节点子树大小以及个数。

具体的解释参考代码，注释很详细。

代码：

#include <iostream>

#include <stdio.h>

using namespace std;

typedef  long long LL;

const LL N=1e18+5;

LL cnt[70];///每一层的残缺节点所在的地方

LL pw[70];///每一层的所有的节点的个数

int deep;

LL n,k,m,ans,L,R,mid;

void dfs(int x)

{

    /*

    L：左兄弟节点往下的所有节点的个数

    R：右兄弟节点往下的所有节点的个数

    mid：残缺节点往下的所有的节点的个数

    */

    if(x>deep) return ;

    dfs(x+1);

    LL pos=(cnt[x]-1)%k; ///pos表示的是于那个残缺节点同父节点的左边的兄弟节点个数

    int f=(cnt[x]-1)&1;///左边的兄弟节点个数的奇偶性，奇数才异或一次

    if(f) ans^=L;

    f=(pw[x]-cnt[x])&1;///同理右边的子树个数的奇偶性

    if(f) ans^=R;

    ans^=mid;

    mid=pos*L+mid+1+(k-pos-1)*R;

    L=L*k+1;///左边一个子树上的节点个数

    R=R*k+1;///右边一个子树上的节点个数

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%lld%lld",&n,&k);

        if(k == 1)///为1的情况单独考虑

        {

            if(n%4 == 0) ans = n;

            else if(n%4 == 1) ans = 1;

            else if(n%4 == 2) ans = n+1;

            else if(n%4 == 3) ans = 0;

            printf("%lld\n",ans);

            continue;

        }

        LL tmp=1;

        m=n-1;

        pw[0]=1;///pw表示的是每一层的节点个数

        for(int i=1; i<70; i++)

        {

            tmp=tmp*k;

            pw[i]=tmp;

            if(m<tmp || tmp<0 )

            {

                pw[i]=N;

                deep=i;

                break;

            }

            m-=tmp;

        }

        cnt[deep]=m;///最后一层不满有m个

        if(m==0)///最后一层为0个的话，相当于上一层正好铺满往上移一层

        {

            deep--;

            m=cnt[deep]=pw[deep];

        }

        ///之后的每一层

        for(int i=deep-1; i>=0; i--)

        {

            cnt[i]=(m+k-1)/k;

            m=cnt[i];

        }

        L=1;

        mid=1;

        R=0;

        ans=0;

        dfs(0);

        printf("%lld\n",ans);

    }

    return 0;

}