这一题开始一看到那么大的数就懵逼了，BFS肯定会TLE。
根据子节点和父节点的关系可以从下往上递归找出p/q对应的层数。根据input中p,q的大小关系可以判定出是左节点还是右节点。因为是二叉树又是层序遍历，num of 第l层最右的node就是sum_{i=0}^l 2^l。如果p/q在l层，n=num of l-1层最右的node+(num of father-{l-1层第一个节点的num})*2+1(if 左节点) or 2(if 右节点)
用记忆化搜索即可，因为对应的二叉树是固定的，每个test case前不必清空，可以省时间。
PS：我开始以为p and q互质还敲了个quick gcd，后来发现并不要考虑这一点。
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<string>
#include<cmath>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
using namespace std;
int P;
int K;
int p;
int q;
map<pair<int,int>,int>level;
map<pair<int,int>,pair<int,int> >fa;
map<pair<int,int>,int>num;
int levelnum[50];
void init()
{
memset(levelnum,0,sizeof(levelnum));
int prod=1;
levelnum[1]=1;
for(int i=2;i<50;i++)
{
prod*=2;
levelnum[i]=levelnum[i-1]+prod;
}
}
int quickgcd(int a,int b)
{
if(a==0) return b;
if(b==0) return a;
if(!(a&1)&&!(b&1))
{
return quickgcd(a>>1,b>>1)<<1;
}
else if(!(b&1))
{
return quickgcd(a,b>>1);
}
else if(!(a&1)) return quickgcd(a>>1,b);
else return quickgcd(abs(a-b),min(a,b));
}
int dfslevel(int x,int y)
{
//cout<<x<<" level "<<y<<endl;
pair<int,int>p=make_pair(x,y);
if(x==1&&y==1)
{
level[p]=1;
fa[p]=make_pair(0,0);
return level[p];
}
if(level[p]!=0)
{
return level[p];
}
else
{
if(x>y)//right
{ //use gcd later
// int fax=x-y;
// int fay=y;
// int facfa=quickgsc(fax,fay);
// fax=fax/facfa;
// fay=fay/facfa;
fa[p]=make_pair(x-y,y);
level[p]=dfslevel(x-y,y)+1;
return level[p];
}
else if(x<y)
{
// int fax=x-y;
// int fay=y;
// int facfa=quickgsc(fax,fay);
fa[p]=make_pair(x,y-x);
level[p]=dfslevel(x,y-x)+1;
return level[p];
}
}
}
int dfsnum(int x,int y)
{
pair<int,int>p=make_pair(x,y);
if(x==1&&y==1)
{
return num[p]=1;
}
if(num[p]!=0)
{
return num[p];
}
if(x>y)//right
{
pair<int,int>q=fa[p];
int falevel=level[q];
int remain=(dfsnum(q.first,q.second)-levelnum[level[fa[q]]]-1)*2+2;
num[p]=levelnum[falevel]+remain;
return num[p];
}
if(x<y)//left
{
pair<int,int> q =fa[p];
int falevel=level[q];
int remain=(dfsnum(q.first,q.second)-levelnum[level[fa[q]]]-1)*2+1;
num[p]=levelnum[falevel]+remain;
return num[p];
}
}
int main()
{
//freopen("input.txt","r",stdin);
//cout<<log(pow(2,32)-1)/log(2)<<endl;
init();
scanf("%d",&P);
for(int ca=0;ca<P;ca++)
{
scanf("%d %d/%d",&K,&p,&q);
int fac=quickgcd(p,q);
p=p/fac;
q=q/fac;//fac=1?
//cout<<p<<" "<<q<<endl;
int l=dfslevel(p,q);
//cout<<l<<endl;
printf("%d %d\n",K,dfsnum(p,q));
}
}