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