题目大意：

给你一颗 n 个节点的完全 k 叉树，问你这棵树中所有子树结点个数的总异或值。

分析：

首先是一个比较常见的结论，对于任意两个数 x y：x=x^y^y；
所以对于一颗完全 k 叉树，假设它有 t 层，那么我可以将它分解成三份，一份是若干个 t-1 层的满 k 叉树，一份若干个 t-2 层的满 k 叉树，还有一颗 t-1 层的不满的完全 k 叉树。因为异或运算的特殊性质，我就根据满 k 叉树的个数的奇偶和层数 t 就可以以接近 t 的时间复杂度得到每一份的答案（如果初始化，就能在O(1)内得到了）。同时相当于减小了所求树的规模，还是以 k 分的速度减少，这就很快了。
最后要注意：k=1的时候要特判，就是输出几百个找下规律就好了。

代码：

#include<bits/stdc++.h>
using namespace std;
long long int n,k;

long long int comf(long long int x)//对于一颗深度为 x 层的满树，返回它的异或值
{
    if(x<=0)return 0;
    if(x==1)return 1;
    long long int ans=1;
    if(k%2==0)
    {
        long long int temp=1;
        for(long long int i=1;i<x;i++)
        {
            temp*=k;
            ans+=temp;
        }
    }
    else
    {
        long long int temp=1;
        for(long long int i=1;i<=x;i++)
        {
            temp*=k;
            temp++;
            ans=ans^temp;
        }
    }
    return ans;
}

long long int sum(long long int x)//返回x层的满树有多少结点
{
    if(x<=0)return 0;
    if(x==1)return 1;
    long long int ans=1;
    for(long long int i=1;i<x;i++)
    {
        ans*=k;
        ans++;
    }
    return ans;
}

long long int f(long long int n)//对于一颗 k 叉树，返回他的异或值
{
    if(n==1)//只有一层
    {
        return 1;
    }
    /*if(n==2) { return 1^2; }*/
    long long int temp=n-1;
    long long int ln,rn;
    long long int x=1;//层数
    while((temp-1)/k>0)
    {
        temp=(temp-1)/k;
        x++;
    }
    x++;
    if(n==sum(x))return comf(x);
    ln=temp-1;
    rn=k-temp;
    long long int ans=n;
    //cout<<temp<<endl;
    if(ln%2==1)
    {
        ans=ans^comf(x-1);
    }
    if(rn%2==1)
    {
        ans=ans^comf(x-2);
    }
    n=n-ln*sum(x-1)-rn*sum(x-2)-1;
    //cout<<x-2;
    //cout<<n;
    ans=ans^f(n);
    return ans;
}


int test=0;
int main()
{
    /*test long long int ans=0; for(int i=1;i<=10000;i++) { ans=ans^i; printf("%d %lld\n",i,ans); } */

    scanf("%d",&test);
    while(test--)
    {
        scanf("%lld%lld",&n,&k);
        if(k!=1)printf("%lld\n",f(n));
        else printf("%lld\n",n%4==1?1:(n%4==2?n+1:(n%4==3?0:n)));
    }
}