Project Euler 198

题目

Ambiguous Numbers

A best approximation to a real number $x$ for the denominator bound $d$ is a rational number $\dfrac{r}{s}$ (in reduced form) with $s \le d$, so that any rational number $\dfrac{p}{q}$ which is closer to $x$ than $\dfrac{r}{s}$ has $q > d$.

Usually the best approximation to a real number is uniquely determined for all denominator bounds. However, there are some exceptions, e.g. $\dfrac{9}{40}$ has the two best approximations $\dfrac{1}{4}$ and $\dfrac{1}{5}$ for the denominator bound $6$. We shall call a real number $x$ ambiguous, if there is at least one denominator bound for which $x$ possesses two best approximations. Clearly, an ambiguous number is necessarily rational.

How many ambiguous numbers $x=\dfrac{p}{q}$, $0 < x < \dfrac{1}{100}$, are there whose denominator $q$ does not exceed $10^8$?

解决方案

如果存在一个正整数$m$，使得两个分数$x=\dfrac{a}{c},y=\dfrac{b}{d}$在第$m$个Farey序列是相邻的。那么$\dfrac{x+y}{2}$很明显是一个答案。

因此，可以考虑对Stern-Brocot Tree进行遍历，枚举出Farey序列中有可能在Farey序列中相邻的分数，并统计。

令$R=100$。为了减少枚举量，对于枚举出的两个分数$x,y$，如果$x\ge\dfrac{1}{R}$，那么没有必要在这个区间上继续寻找答案（此时这里计算出来的$\dfrac{x+y}{2}$都大于$\dfrac{1}{R}$，不合题意）。

另外，由于直接使用递归会造成栈溢出（分析代码不难知道，最大的递归深度将会达到$O(N)$级别），因此这里使用非递归的方式遍历Stern-Brocot Tree.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100000000;
const int R=100;
struct S{
    ll a,c,b,d;
};
int main(){
    int ans=0;
    stack<S>st;
    st.push(S{0,1,1,1});
    while(!st.empty()){
        S s=st.top();st.pop();
        ll a=s.a,b=s.b,c=s.c,d=s.d;
        if(c*d*2>N) continue;
        // 左边的分数已经大于等于1/R，没必要取下去。
        if(a*R>=c) continue;
        ll p=a+b,q=c+d;
        ll u=a*d+b*c,v=c*d*2;
        if(u*R<v) ++ans;
        st.push(S{a,c,p,q});
        st.push(S{p,q,b,d});
    }
    printf("%d\n",ans);
}