TIOJ 1101 . D.分「樹」

#include <cstdio>

#include <cstdlib>

struct frac{

    int a, b;

    frac(int _a, int _b): a(_a), b(_b){}

    void print(){printf("(%d, %d)", a, b);}

};

frac operator+(frac f1, frac f2){return frac(f1.a+f2.a, f1.b+f2.b);}

int main(){

    int p, q;

    for(;;){

        scanf("%d %d", &p, &q);

        if(!p&&!q) break;

        if(p == 1 and q == 1){puts("0/1");continue;}

        if(p == 1 and q == 2){puts("1/0");continue;}

        if(p == 2 and q == 1){puts("1/1");continue;}

        q--;

        frac l(0,1), m(1,1), r(1,0);

        for(int lx = p;lx>=3;lx--){

            if(q & (1<<(lx-3))) l = m;

            else r = m;

            m =(l+r);

            //l.print(); m.print(); r.print(); puts("");

        }

        printf("%d/%d\n", m.a, m.b);

    }

    return 0;

}