令$f(n)$为将n表达为2的幂之和、且每种幂至多使用两次的方式总数，并规定$f(0)=1$。

例如$f(10)=5$，即有五种不同的方式表示10： \begin{align*} 10&=1+1+8 10&=1+1+4+4 10&=1+1+2+2+4 10&=2+4+4 10&=2+8 \end{align*} 已知对任意分数$p/q$（p、q都是正整数）都能找到至少一个正整数n，使得$f(n)/f(n-1)=p/q$。

例如使得$f(n)/f(n-1)=13/17$的最小n是241，其二进制表示为11110001。从左往右读这个二进制串得：4个1、3个0、1个1，因此可以将它简写作$4,3,1$。

求满足$f(n)/f(n-1)=123456789/987654321$的最小的n的二进制简写。

本题难度:

解答

由第169题的分析可知 $$f(n)=\begin{cases}1 & n\le 1 \\ f(\frac{n-1}{2}) & n \text{ odd} \\ f(\frac{n}{2})+f(\frac{n-2}{2}) & n \text{ even}\end{cases}$$ 因此 $$f(2k+1)=f(k), \quad f(2k)=f(k)+f(k-1), \quad f(2k-1)=f(k-1)$$ 从而若n是奇数则$f(n)/f(n-1)< 1$，若n是偶数则$f(n)/f(n-1)>1$，因此可以用类似于辗转相除的方法从低位到高位计算出n的二进制表达。

结果是$1,13717420,8$。

a,b,s=123456789,987654321,[]

while a>1 and b>1:
    if a>b:
        if a%b>0:
            s.append(str(a/b))
            a%=b
        else:
            s.append(str(a/b-1))
            s.append("1")
            a=0
    else:
        s.append(str(b/a))
        b%=a
print ",".join(s[::-1])