Artifact bfa0be1fa6ea3c75c678e1a1b27ac92f68d0a561
//-------------------------------------------------------------
// Enumerate all positive reduced fractions in a
// systematic manner.
// [pl/ql, pr/qr] --> [pl/ql, pm/qm] + [pm/qm, pr/qr]
// --> ...
//
// Verified by
// - CodeCraft 09 FRACTION
//-------------------------------------------------------------
void sternBrocot(LL pl = 0, LL ql = 1, LL pr = 1, LL qr = 0)
{
LL pm = pl + pr, qm = ql + qr;
sternBrocot(pl, ql, pm, qm);
sternBrocot(pm, qm, pr, qr);
}
/*
bool fleq(LL p1, LL q1, LL p2, LL q2)
{
return p1*q2 <= p2*q1;
}
void sternBrocot(LL pl = 0, LL ql = 1, LL pr = 1, LL qr = 0)
{
for(;;) {
LL pm = pl + pr, qm = ql + qr;
if( fleq(c,d,pm,qm) ) {
// pr = pm, qr = qm; // [pl/ql, pm/qm]
LL X = c*ql - d*pl;
LL Y = d*pr - c*qr;
LL k = max(1LL, Y/X);
pr += k*pl;
qr += k*ql;
}
else if( fleq(pm,qm,a,b) ) {
// pl = pm, ql = qm; // [pm/qm, pr/qr]
LL X = b*pr - a*qr;
LL Y = a*ql - b*pl;
LL k = max(1LL, Y/X);
pl += k*pr;
ql += k*qr;
}
else {
cout << pm+qm*base << "/" << qm << endl;
break;
}
}
}
*/