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