bzoj2187
多组询问，每次给出 $a, b, c, d$，求满足 $frac{a}{b} < frac{p}{q} < frac{c}{d}$ 的所有二元组 $(p, q)$ 中 $p$ 为第一关键字，$q$ 为第二关键字排出来的字典序最小的那一对。
分析:
设计函数 $f(a,b,p,q,c,d)$.
按照题目中保证 $q$ 最小的要求考虑该函数的几个边界：
1. $left lfloor frac{a}{b} ight floor-1 leq left lceil frac{c}{d} ight ceil-1$，这个时候 $p = left lfloor frac{a}{b} ight floor+1, q=1$ 时字典序最小
2. $a=0$ 时，这个时候 $0 < frac{p}{q} < frac{c}{d} Rightarrow q > frac{dp}{c}$，显然 $p=1, q=left lfloor frac{c}{d} ight floor+1$ 时字典序最小
然后考虑辗转相除缩小问题规模：
1. $a > b or c > d$：原式等价于：$frac{a\%b}{b} < frac{p}{q}-left lfloor frac{a}{b} ight floor < frac{c}{d}-left lfloor frac{a}{b} ight floor$
即：$f(a, b, p, q, c,d) = f(a \% b, b, p, q, c-{left lfloor frac{a}{b} ight floor}d), p+= {left lfloor frac{a}{b} ight floor}q$.
2. $a leq b and c leq d$：原式等价于：$frac{d}{c} < frac{q}{p} < frac{b}{a}$.
即：$f(a,b,p,q,c,d) = f(d,c,q,p,b,a)$，这样就回到了第一步。
#include<bits/stdc++.h> 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 f(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){q=1, p=x; return;} if(a <= b && c <= d) f(d, c, q, p, b, a); else{ f(a%b, b, p, q, c-a/b*d, d); p += a/b*q;} } int main() { while(scanf("%lld%lld%lld%lld", &a, &b, &c, &d) == 4) { f(a, b, p, q, c, d); printf("%lld/%lld ", p, q); } return 0; }
hdu3637
给出两个非负有理数 $A, B$（$A < B$），你的任务是发现一个分数介于A和B，在这个区间内可能有许多分数，请输出分子加分母和最小的分数。
分析：
首先，解决输入问题，无线循环小数很容易转换成分数。
因为0.[1]=1/9, 0.0[1]=1/99, 0.00[1]=1/999...
将小数分成括号部分和非括号部分即可。
问题转换成求 $frac{a}{b} < frac{p}{q} < frac{c}{d}$，且 $p+q$ 最小。
可以推导出 $p$ 最小时，$p+q$ 就最小，于是套类欧几里得模板即可。
//交上去会MLE，不知道咋解决
#include<bits/stdc++.h> 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 f(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){q=1, p=x; return;} if(a <= b && c <= d) f(d, c, q, p, b, a); else{ f(a%b, b, p, q, c-a/b*d, d); p += a/b*q;} } char s[50]; void input(ll& a, ll& b) { scanf("%s", s); int len = strlen(s); ll tmp1 = 0, tmp2 = 0, flag = 0, is_point=0, is_kh=0, cnt1=1, cnt2=0; for(int i = 0;i < len;i++) { if(s[i] == ']') continue; if(s[i] == '.'){is_point=1;continue;} if(s[i] == '['){is_kh=1;continue;} if(is_point&&!is_kh) cnt1 = cnt1*10; if(is_point) cnt2 = cnt2*10+9; if((!is_kh)) tmp1 = tmp1*10 + (s[i]-'0'); else tmp2 = tmp2*10 + (s[i]-'0'); } calc(tmp1, cnt1); if(cnt2 == 0) { calc(tmp2, cnt2); a = tmp1, b=cnt1; } else a = tmp1*cnt2+tmp2*cnt1, b=cnt1*cnt2; if(!a) calc(a, b); } int main() { int T, kase=0; scanf("%d", &T); while(T--) { input(a, b);input(c, d); //printf("%lld %lld %lld %lld ", a, b, c, d); f(a, b, p, q, c, d); printf("Case %d: %lld/%lld ", ++kase, p, q); } return 0; }
参考链接：
1. https://blog.csdn.net/dreaming__ldx/article/details/86769792