Artifact bfa0be1fa6ea3c75c678e1a1b27ac92f68d0a561:
0000: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 0a 2f 2f 20 45 6e 75 6d 65 72 61 74 65 20 61 6c .// Enumerate al
0050: 6c 20 70 6f 73 69 74 69 76 65 20 72 65 64 75 63 l positive reduc
0060: 65 64 20 66 72 61 63 74 69 6f 6e 73 20 69 6e 20 ed fractions in
0070: 61 20 0a 2f 2f 20 73 79 73 74 65 6d 61 74 69 63 a .// systematic
0080: 20 6d 61 6e 6e 65 72 2e 0a 2f 2f 20 20 20 5b 70 manner..// [p
0090: 6c 2f 71 6c 2c 20 70 72 2f 71 72 5d 20 2d 2d 3e l/ql, pr/qr] -->
00a0: 20 5b 70 6c 2f 71 6c 2c 20 70 6d 2f 71 6d 5d 20 [pl/ql, pm/qm]
00b0: 2b 20 5b 70 6d 2f 71 6d 2c 20 70 72 2f 71 72 5d + [pm/qm, pr/qr]
00c0: 0a 2f 2f 20 20 20 20 20 20 20 20 20 20 20 20 20 .//
00d0: 20 20 20 20 20 2d 2d 3e 20 2e 2e 2e 0a 2f 2f 0a --> ....//.
00e0: 2f 2f 20 56 65 72 69 66 69 65 64 20 62 79 0a 2f // Verified by./
00f0: 2f 20 20 20 2d 20 43 6f 64 65 43 72 61 66 74 20 / - CodeCraft
0100: 30 39 20 46 52 41 43 54 49 4f 4e 0a 2f 2f 2d 2d 09 FRACTION.//--
0110: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0120: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0130: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0140: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 76 6f 69 -----------..voi
0150: 64 20 73 74 65 72 6e 42 72 6f 63 6f 74 28 4c 4c d sternBrocot(LL
0160: 20 70 6c 20 3d 20 30 2c 20 4c 4c 20 71 6c 20 3d pl = 0, LL ql =
0170: 20 31 2c 20 4c 4c 20 70 72 20 3d 20 31 2c 20 4c 1, LL pr = 1, L
0180: 4c 20 71 72 20 3d 20 30 29 0a 7b 0a 09 4c 4c 20 L qr = 0).{..LL
0190: 70 6d 20 3d 20 70 6c 20 2b 20 70 72 2c 20 71 6d pm = pl + pr, qm
01a0: 20 3d 20 71 6c 20 2b 20 71 72 3b 0a 09 73 74 65 = ql + qr;..ste
01b0: 72 6e 42 72 6f 63 6f 74 28 70 6c 2c 20 71 6c 2c rnBrocot(pl, ql,
01c0: 20 70 6d 2c 20 71 6d 29 3b 0a 09 73 74 65 72 6e pm, qm);..stern
01d0: 42 72 6f 63 6f 74 28 70 6d 2c 20 71 6d 2c 20 70 Brocot(pm, qm, p
01e0: 72 2c 20 71 72 29 3b 0a 7d 0a 0a 2f 2a 0a 62 6f r, qr);.}../*.bo
01f0: 6f 6c 20 66 6c 65 71 28 4c 4c 20 70 31 2c 20 4c ol fleq(LL p1, L
0200: 4c 20 71 31 2c 20 4c 4c 20 70 32 2c 20 4c 4c 20 L q1, LL p2, LL
0210: 71 32 29 0a 7b 0a 09 72 65 74 75 72 6e 20 70 31 q2).{..return p1
0220: 2a 71 32 20 3c 3d 20 70 32 2a 71 31 3b 0a 7d 0a *q2 <= p2*q1;.}.
0230: 0a 76 6f 69 64 20 73 74 65 72 6e 42 72 6f 63 6f .void sternBroco
0240: 74 28 4c 4c 20 70 6c 20 3d 20 30 2c 20 4c 4c 20 t(LL pl = 0, LL
0250: 71 6c 20 3d 20 31 2c 20 4c 4c 20 70 72 20 3d 20 ql = 1, LL pr =
0260: 31 2c 20 4c 4c 20 71 72 20 3d 20 30 29 0a 7b 0a 1, LL qr = 0).{.
0270: 09 66 6f 72 28 3b 3b 29 20 7b 0a 09 09 4c 4c 20 .for(;;) {...LL
0280: 70 6d 20 3d 20 70 6c 20 2b 20 70 72 2c 20 71 6d pm = pl + pr, qm
0290: 20 3d 20 71 6c 20 2b 20 71 72 3b 0a 0a 09 09 69 = ql + qr;....i
02a0: 66 28 20 66 6c 65 71 28 63 2c 64 2c 70 6d 2c 71 f( fleq(c,d,pm,q
02b0: 6d 29 20 29 20 7b 0a 2f 2f 09 09 09 70 72 20 3d m) ) {.//...pr =
02c0: 20 70 6d 2c 20 71 72 20 3d 20 71 6d 3b 20 2f 2f pm, qr = qm; //
02d0: 20 5b 70 6c 2f 71 6c 2c 20 70 6d 2f 71 6d 5d 0a [pl/ql, pm/qm].
02e0: 09 09 09 4c 4c 20 58 20 3d 20 63 2a 71 6c 20 2d ...LL X = c*ql -
02f0: 20 64 2a 70 6c 3b 0a 09 09 09 4c 4c 20 59 20 3d d*pl;....LL Y =
0300: 20 64 2a 70 72 20 2d 20 63 2a 71 72 3b 0a 09 09 d*pr - c*qr;...
0310: 09 4c 4c 20 6b 20 3d 20 6d 61 78 28 31 4c 4c 2c .LL k = max(1LL,
0320: 20 59 2f 58 29 3b 0a 09 09 09 70 72 20 2b 3d 20 Y/X);....pr +=
0330: 6b 2a 70 6c 3b 0a 09 09 09 71 72 20 2b 3d 20 6b k*pl;....qr += k
0340: 2a 71 6c 3b 0a 09 09 7d 0a 09 09 65 6c 73 65 20 *ql;...}...else
0350: 69 66 28 20 66 6c 65 71 28 70 6d 2c 71 6d 2c 61 if( fleq(pm,qm,a
0360: 2c 62 29 20 29 20 7b 0a 2f 2f 09 09 09 70 6c 20 ,b) ) {.//...pl
0370: 3d 20 70 6d 2c 20 71 6c 20 3d 20 71 6d 3b 20 2f = pm, ql = qm; /
0380: 2f 20 5b 70 6d 2f 71 6d 2c 20 70 72 2f 71 72 5d / [pm/qm, pr/qr]
0390: 0a 09 09 09 4c 4c 20 58 20 3d 20 62 2a 70 72 20 ....LL X = b*pr
03a0: 2d 20 61 2a 71 72 3b 0a 09 09 09 4c 4c 20 59 20 - a*qr;....LL Y
03b0: 3d 20 61 2a 71 6c 20 2d 20 62 2a 70 6c 3b 0a 09 = a*ql - b*pl;..
03c0: 09 09 4c 4c 20 6b 20 3d 20 6d 61 78 28 31 4c 4c ..LL k = max(1LL
03d0: 2c 20 59 2f 58 29 3b 0a 09 09 09 70 6c 20 2b 3d , Y/X);....pl +=
03e0: 20 6b 2a 70 72 3b 0a 09 09 09 71 6c 20 2b 3d 20 k*pr;....ql +=
03f0: 6b 2a 71 72 3b 0a 09 09 7d 0a 09 09 65 6c 73 65 k*qr;...}...else
0400: 20 7b 0a 09 09 09 63 6f 75 74 20 3c 3c 20 70 6d {....cout << pm
0410: 2b 71 6d 2a 62 61 73 65 20 3c 3c 20 22 2f 22 20 +qm*base << "/"
0420: 3c 3c 20 71 6d 20 3c 3c 20 65 6e 64 6c 3b 0a 09 << qm << endl;..
0430: 09 09 62 72 65 61 6b 3b 0a 09 09 7d 0a 09 7d 0a ..break;...}..}.
0440: 7d 0a 2a 2f 0a }.*/.