Day5
T1
简要题意
有两个正整数 \(a<b\le 10^9\)，给出 \(\dfrac{a}{b}\) 的小数点后 \(19\) 位，要求还原 \(a,b\)，保证有解。
solution
一个科技：\(\texttt{Stern-Brocot tree}(SBT)\)，可以参考这个博客学习。
先给出 $O(n)$ 找的代码
#include<bits/stdc++.h>
#define LL long long
#define LD long double
#define int LL
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const LD eps=1e-19;
int A,B;
#define Iabs(x) ((x)>0?(x):-(x))
#define C (x-(LD)(m)/n)
void find(LD x,int a=0,int b=1,int c=1,int d=0)
{
int m=a+c,n=b+d;
if(Iabs(C)<eps) return A=m,B=n,void();
if(x<(LD)(m)/n) return find(x,a,b,m,n);
return find(x,m,n,c,d);
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);LD x;cin>>x;find(x);cout<<A<<" "<<B;
return 0;
}
注意到博客中的一句话：称从 \(SBT\) 上任意一个节点 \(\dfrac{a}{b}\) 沿着相同方向跳到需要换方向的第一个点为一次跳跃，那么该点到根节点至多跳跃 \(O(\log\max(a,b))\) 次。
于是跳的过程中二分优化一下，复杂度 \(O(\log^2 V)\)。
$\texttt{code}$
#include<bits/stdc++.h>
#define LL long long
#define LD long double
#define int LL
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const LD eps=1e-19;
int A,B;
#define Iabs(x) ((x)>0?(x):-(x))
#define C (x-(LD)(m)/n)
void find(LD x,int a=0,int b=1,int c=1,int d=0)
{
int m=a+c,n=b+d,l=1,r=1e9,mid,ans=-1;
if(Iabs(C)<eps) return A=m,B=n,void();
if(x<(LD)(m)/n)
{
while(l<=r)
{
int mid=(l+r)>>1;m=c+mid*a,n=d+mid*b;
if(C>=-eps) ans=mid,r=mid-1;else l=mid+1;
}ans--;
return find(x,a,b,c+ans*a,d+ans*b);
}
while(l<=r)
{
int mid=(l+r)>>1;m=a+mid*c,n=b+mid*d;
if(C<=eps) ans=mid,r=mid-1;else l=mid+1;
}ans--;
return find(x,a+ans*c,b+ans*d,c,d);
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);LD x;cin>>x;find(x);cout<<A<<" "<<B;
return 0;
}