传送门
题意简述：多组询问，每次给出a,b,c,da,b,c,da,b,c,d，求满足ab<pq<cd\frac ab<\frac pq<\frac cdba<qp<dc的所有二元组(p,q)(p,q)(p,q)中qqq为第一关键字，ppp为第二关键字排出来字典序最小的那一对。
思路：
设计函数f(a,b,p,q,c,d)f(a,b,p,q,c,d)f(a,b,p,q,c,d)。
按照题目中保证qqq最小的要求考虑该函数几个边界：
- ⌊ab⌋+1≤⌈cd⌉−1\left\lfloor\frac ab\right\rfloor+1\le\left\lceil\frac cd\right\rceil-1⌊ba⌋+1≤⌈dc⌉−1，这个时候p=⌊ab⌋+1,q=1p=\left\lfloor\frac ab\right\rfloor+1,q=1p=⌊ba⌋+1,q=1时字典序最小。
- a=0a=0a=0，这个时候0<pq<cd⇒q>dpc0<\frac pq<\frac cd\Rightarrow q>\frac{dp}c0<qp<dc⇒q>cdp，显然p=1,q=⌊cd⌋+1p=1,q=\left\lfloor\frac cd\right\rfloor+1p=1,q=⌊dc⌋+1的时候字典序最小。
然后考虑如何辗转缩小问题规模：
- a>ba>ba>b ororor c>d:原式⇔a%bb<pq−⌊ab⌋<cd−⌊ab⌋c>d:原式\Leftrightarrow\frac{a\%b}b<\frac pq-\left\lfloor\frac ab\right\rfloor<\frac cd-\left\lfloor\frac ab\right\rfloorc>d:原式⇔ba%b<qp−⌊ba⌋<dc−⌊ba⌋
⇒f(a,b,p,q,c,d)=f(a%b,b,p,q,c−⌊ab⌋d,d),p+=⌊ab⌋q\Rightarrow f(a,b,p,q,c,d)=f(a\%b,b,p,q,c-\left\lfloor\frac ab\right\rfloor d,d),p+=\left\lfloor\frac ab\right\rfloor q⇒f(a,b,p,q,c,d)=f(a%b,b,p,q,c−⌊ba⌋d,d),p+=⌊ba⌋q - a≤ba\le ba≤b andandand c≤d:原式⇔dc<qp<bac\le d:原式\Leftrightarrow \frac dc<\frac qp<\frac bac≤d:原式⇔cd<pq<ab
⇒f(a,b,p,q,c,d)=f(d,c,q,p,b,a)\Rightarrow f(a,b,p,q,c,d)=f(d,c,q,p,b,a)⇒f(a,b,p,q,c,d)=f(d,c,q,p,b,a)这样会回到第一步。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
ll a,b,c,d,p,q;
inline ll gcd(ll a,ll b){while(b){ll t=a;a=b,b=t-t/a*a;}return a;}
inline void calc(ll&a,ll&b){ll d=gcd(a,b);a/=d,b/=d;}
inline void solve(ll a,ll b,ll&p,ll&q,ll c,ll d){
calc(a,b),calc(c,d);
if(!a){p=1,q=d/c+1;return;}
ll x=a/b+1,y=c/d+(c%d>0)-1;
if(x<=y){p=x,q=1;return;}
if(a<=b&&c<=d)return solve(d,c,q,p,b,a);
solve(a-a/b*b,b,p,q,c-d*(a/b),d),p+=q*(a/b);
}
int main(){
while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&d))solve(a,b,p,q,c,d),printf("%lld/%lld\n",p,q);
return 0;
}