【ACdream 1187】Rational Number Tree(树,递归)

#include<iostream>
#define ll unsigned long long
using namespace std;
ll n,p,q,ans;
void solve(ll n){
    if(n==1){
        p=1;
        q=1;
        return;
    }
    solve(n>>1);
    if(n%2)
        p+=q;
    else
        q+=p;
}
void work(){
    if(p==q){
        ans=1;
        return;
    }
    if(p>q){
        p-=q;
        work();
        ans=ans<<1|1;
    }else{
        q-=p;
        work();
        ans<<=1;
    }
}
int main(){
    int t,op;
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>op;
        cout<<"Case #"<<i<<": ";
        if(op==1){
            cin>>n;
            solve(n);
            cout<<p<<" "<<q<<"\n";
        }else{
            cin>>p>>q;
            work();
            cout<<ans<<"\n";
        }
    }
}