Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

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$ \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≤1018)$.

Output

For each test case:
A single line contains a nonnegative integer, denoting the answer.

Sample Input

[cpp]
2
5 2
5 3
[/cpp]

Sample Output

[cpp]
7
6
[/cpp]

Source

2017 Multi-University Training Contest – Team 7

题解:

赛后发现非常可写。只是我不知道从1开始异或的规律(逃)。
从一开始连续异或到 n 的连续XOR值
if n % 4==1 XOR= 1
if n % 4==2 XOR= n+1
if n % 4==3 XOR= 0
if n % 4==0 XOR= n

Code

[cpp]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int t;scanf(“%d”,&t);
while(t–) {
ll n,k;scanf(“%lld%lld”,&n,&k);
if(k==1) {
ll kase = n%4;
if(kase==1) printf(“1\n”);
else if(kase==2) printf(“%lld\n”,n+1);
else if(kase==3) printf(“0\n”);
else printf(“%lld\n”,n);
continue;
}
//n==27 k==3
ll ans = n; //i’s par = (i-1)/k
while(1) {
if(n-1<=k) {
if((n-1)%2) ans ^= 1;
break;
}
ll now = 1, x = 1;//x 全满k叉树当前层的节点总数, now 当前层的最左边节点序号
while(now + xk<=n-1)
x *= k, now += x;
ll last = n – now;//最后一层节点数
ll l = (last-1)/x;//唯一 一颗不满k叉树得左边合法树对应的父节点个数
ll r = k-l-1;//右边已合法树对应父亲节点的个数
if(l%2==1) ans ^= now;//
if(r%2==1) ans ^= (now-x);
n -= l
now + r*(now-x)+1;
ans ^= n;
}
printf(“%lld\n”,ans);
}
}

[/cpp]

分类: 图论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.