P5179 Fraction
Genius_Star · · 题解
或许更好的阅读体验。
前置知识。
怎么题解区的 Stern-Brocot 树怎么都在递归去做，来一篇 Stern-Brocot 树的依靠树性质的单
思路：
首先看看 Stern-Brocot 树的图：
显然这是一颗二叉搜索树，考虑
-
令
\frac{x}{y} = \operatorname{LCA}(\frac{a}{b}, \frac{c}{d}) 。 -
若
\frac{x}{y} \ne \frac{a}{b} 且\frac{x}{y} \ne \frac{c}{d} ：即\frac{a}{b} 与\frac{c}{d} 分别在\frac{x}{y} 的左右儿子的子树中，说明必然\frac{a}{b} < \frac{x}{y} < \frac{c}{d} ，考虑证明\frac{x}{y} 就是最优答案；显然的，\frac{x}{y} 子树内的分数\frac{x'}{y'} 必然满足x' \ge x, y' \ge y （因为都是以\frac{x}{y} 为基础合并出来的），于是子树内满足条件的没有\frac{x}{y} 优；而子树外的显然不可能在(\frac{a}{b}, \frac{c}{d}) 之间。 -
否则
\frac{a}{b} 与\frac{c}{d} 在一条链上，这里只说\frac{c}{d} 是其\operatorname{LCA} 的情况，另一种对称类似即可：显然\frac{a}{b} 在\frac{c}{d} 的左儿子lson 子树中，那么直接选左儿子作为\frac{p}{q} 行吗？不行，因为若\frac{a}{b} 在lson 的右子树内，那么就不满足条件了，所以再分讨一下：-
若
\frac{a}{b} 在lson 的左子树内：那么lson 是最优的，证明类似。 -
否则
\frac{a}{b} = lson 或者在lson 的右子树内怎么办？容易想到，考虑\frac{a}{b} 的位置，从lson 出发后一直往右跳，直到\frac{a}{b} 在当前点左子树中或者等于当前点：-
若
\frac{a}{b} 等于当前点：那么最优的是\frac{a}{b} 的右儿子。 -
否则
\frac{a}{b} 在当前点的左子树中：那么最优的就是当前点。
-
-
大家可以自己手摸感受一下。
于是直接在应用 Stern-Brocot 树模版，找到
完整代码：
#include<bits/stdc++.h>
#define int long long
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define lowbit(x) x & (-x)
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
#define mkp(x, y) make_pair(x, y)
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
inline ll read(){
ll x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
inline void write(ll x){
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
inline pair<int, int> getLR(vector<pair<char, int>> s){
int len = s.size();
int m = 0, n = 1, m_ = 1, n_ = 0;
for(int i = 0; i < len; ++i){
if(s[i].fi == 'L')
m_ = s[i].se * m + m_, n_ = s[i].se * n + n_;
else
m = m + s[i].se * m_, n = n + s[i].se * n_;
}
return mkp(m + m_, n + n_);
}
inline vector<pair<char, int>> backLR(int m, int n){
vector<pair<char, int>> ans;
while(m && n && m != n){
if(m < n){
if(n % m == 0)
ans.push_back({'L', n / m - 1});
else
ans.push_back({'L', n / m});
n = n % m;
}
else{
if(m % n == 0)
ans.push_back({'R', m / n - 1});
else
ans.push_back({'R', m / n});
m = m % n;
}
}
return ans;
}
inline pair<int, int> getkfa(int m, int n, int k){
auto V = backLR(m, n);
int sum = 0, len = V.size();
for(int i = 0; i < len; ++i)
sum += V[i].se;
if(sum < k)
return mkp(-1, -1);
vector<pair<char, int>> fa;
for(int i = 0; i < len; ++i){
if(!k)
break;
if(V[i].se <= k){
fa.push_back(V[i]);
k -= V[i].se;
}
else{
fa.push_back(mkp(V[i].fi, k));
k = 0;
}
}
return getLR(fa);
}
inline pair<pair<int, int>, pair<int, int>> range(int p, int q){
auto s = backLR(p, q);
int len = s.size();
int m = 0, n = 1, m_ = 1, n_ = 0;
for(int i = 0; i < len; ++i){
if(s[i].fi == 'L')
m_ = s[i].se * m + m_, n_ = s[i].se * n + n_;
else
m = m + s[i].se * m_, n = n + s[i].se * n_;
}
return mkp(mkp(m, n), mkp(m_, n_));
}
inline pair<int, int> getlca(int a, int b, int c, int d){
auto A = backLR(a, b), B = backLR(c, d);
int s1 = 0, s2 = 0;
for(auto v : A)
s1 += v.se;
for(auto v : B)
s2 += v.se;
if(s1 < s2){
swap(a, c), swap(b, d);
swap(A, B);
}
vector<pair<char, int>> lca;
int j = 0;
for(int i = 0; i < (int)A.size(); ++i){
int s = A[i].se;
while(j < (int)B.size() && s){
if(B[j].fi != A[i].fi)
break;
if(B[j].se <= s){
s -= B[j].se;
++j;
}
else{
B[j].se -= s;
s = 0;
}
}
if(j == (int)B.size() || s){
lca.push_back(mkp(A[i].fi, A[i].se - s));
break;
}
lca.push_back(A[i]);
}
return getLR(lca);
}
inline int getdep(int m, int n){
int sum = 0;
auto V = backLR(m, n);
for(auto t : V)
sum += t.se;
return sum;
}
int T, a, b, c, d, p, q, len, x, k;
char C;
char op[20];
signed main(){
while(~scanf("%lld%lld%lld%lld", &a, &b, &c, &d)){
int d1 = __gcd(a, b), d2 = __gcd(c, d);
a /= d1, b /= d1, c /= d2, d /= d2;
// cerr << a << ' ' << b << ' ' << c << ' ' << d << '\n';
auto t = getlca(a, b, c, d);
int depa = getdep(a, b), depb = getdep(c, d);
// cerr << depa << ' ' << depb << '\n';
if(t.fi == c && t.se == d){
if(depb + 1 == depa){
auto V = backLR(a, b);
V.push_back(mkp('R', 1));
t = getLR(V);
// cerr << "AA\n";
}
else{
auto V = backLR(c, d);
V.push_back(mkp('L', 1));
t = getLR(V);
if(1ll * t.fi * b < 1ll * a * t.se){
int x = 0;
if(V.size() == 1 || (V[V.size() - 2].fi == 'R'))
x = V.size();
else
x = V.size() - 1;
V = backLR(a, b);
if((int)V.size() == x + 1)
V.push_back(mkp('R', 1));
else{
while((int)V.size() > x + 1)
V.pop_back();
}
t = getLR(V);
}
// cerr << "AB\n";
}
}
else if(t.fi == a && t.se == b){
if(depa + 1 == depb){
auto V = backLR(c, d);
V.push_back(mkp('L', 1));
t = getLR(V);
// cerr << "BA\n";
}
else{
auto V = backLR(a, b);
V.push_back(mkp('R', 1));
t = getLR(V);
if(1ll * t.fi * d > 1ll * c * t.se){
int x = 0;
if(V.size() == 1 || (V[V.size() - 2].fi == 'L'))
x = V.size();
else
x = V.size() - 1;
V = backLR(c, d);
if((int)V.size() == x + 1)
V.push_back(mkp('L', 1));
else{
while((int)V.size() > x + 1)
V.pop_back();
}
t = getLR(V);
}
// cerr << "BB\n";
}
}
write(t.fi);
putchar('/');
write(t.se);
putchar('\n');
}
return 0;
}