两可数

实数x的分母上限为$d\in\mathbb N$的最优有理逼近数，是一个最简分数$r/s$，其中$r,s\in\mathbb Z$，且$1\le s\le d$，使得只要$p,q\in\mathbb Z$满足 $$|\frac{p}{q}-x| < |\frac{r}{s}-x|$$ 就有$q>d$。

一般这种最优逼近是唯一的，不过也存在例外，比如对于$9/40$，$1/4$和$1/5$都是其分母上限为6的最优有理逼近数。

若对实数x，存在$d\in\mathbb N$，使之有两个分母上限为d的最优有理逼近数，就称x为两可数。显然，两可数必定是有理数。

满足$x=p/q$，$p,q\in\mathbb N$，$\gcd(p,q)=1$，$q\le 10^8$且$0 < x < 1/100$的两可数共有多少个？

本题难度:

解答

与第192题的策略相同，只需不断生成法里序列并考察相邻两项的中点是否满足要求、直到无法再生产满足要求的项（左端点大于等于$1/100$或中点的分母超过$10^8$）为止。

最终结果是$52374425$。

n,m,r=100000000,100,0
s=[(0,1,1,1)]
while s:
    a,b,c,d=s.pop()
    p,q,u,v=a+c,b+d,a*d+b*c,b*d*2
    if v <= n:
        if u*m < v:
            r+=1
        if a*m < b:
            s.append((a,b,p,q))
            s.append((p,q,c,d))
print r