# hdu 6121-Build a tree（深搜+思想）

www.MyException.Cn  网友分享于：2013-08-22  浏览：0次
hdu 6121---Build a tree（深搜+思维）

Problem Description
HazelFan wants to build a rooted tree. The tree has

Input
The first line contains a positive integer

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

官方题解：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef  long long LL;
const LL N=1e18+5;
LL cnt[70];
LL pw[70];
LL n,k,m;
int deep;
LL ans=0;
LL L,R,mid;

void dfs(int x)
{
if(x>deep) return ;
dfs(x+1);
LL pos=(cnt[x]-1)%k; ///left brother;

int f=(cnt[x]-1)&1;
if(f) ans^=L;

LL cR=pw[x]-cnt[x];
f=cR&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; cin>>T;
while(T--)
{
scanf("%lld%lld",&n,&k);
if(k == 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;
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;
if(m==0) { deep--; cnt[deep]=pw[deep]; m=cnt[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;
}