From 1161c649837a4ba1b8854ef6a142266905331cfd Mon Sep 17 00:00:00 2001 From: sshwy Date: Wed, 17 Jul 2019 22:31:15 +0800 Subject: [PATCH] =?utf8?q?=E6=B7=BB=E5=8A=A0Stern-Brocot=E6=A0=91=E5=92=8C?= =?utf8?q?Farey=E5=BA=8F=E5=88=97=E7=AE=80=E4=BB=8B?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- docs/misc/images/stern-brocot1.png | Bin 0 -> 31837 bytes docs/misc/stern-brocot.md | 127 +++++++++++++++++++++++++++++++++++++ 2 files changed, 127 insertions(+) create mode 100644 docs/misc/images/stern-brocot1.png create mode 100644 docs/misc/stern-brocot.md diff --git a/docs/misc/images/stern-brocot1.png b/docs/misc/images/stern-brocot1.png new file mode 100644 index 0000000000000000000000000000000000000000..8f1adcb3d61fe561f3f8b8b0a9ed06f47528d81b GIT binary patch literal 31837 zcmd?QbyO7W+b%jmC>=_N!q7+~4Jrr>T}p=_EiIj+uL4Tw&{9h22udR*j52_<;Lso= z2uOoS*M7$L_pSY%ea<>-@4vUYmI}{2amRIEcMxx6phZo=Mgf69sFB(lCJ+b-_$SQe z92xlQv%~LG@E4h*u9gPmjQIQI$JZ$k$R!9;LjE;G}(T3`??ciCfu7HzZD2hTz&FYJD_IJweX6LlCRaae8P(+He$B^QFmj$3n+*1g7Smw5|)+=7n~0Dc>VU zI~gQe$Cck#?POBN&;@~3!*f9axA)OJgXl1{xEm|zcy2O>lHXSi#$#t;I=b4 z*!$<-m6VXVLgD5saO_S0dq z9m&dv6n+R~I~jTof-S^Cu{W{mSStc6fs7y?qx-wy|JU^K_J%<*cNAGN<-12MpvNUp zOCY>bIoM>ARw%jyq7Xmc2JqEvqE_zi-9`nE9earqwP{UTIiy5HrfcL z%%-$O>enA5E^dZuwvv=1kZX6%2@HhG4%C~<6)YB+naDsF*q&)lFH!J#eLKqICvIoy z_kM)7xr>L#*qh~VTRUuMK1xGia0^hw!Pa+WGcB3S@0xZX)hJq+Vbv1(94Q28A{U~z z$uPL9Lcwv>;mmEKhZM^@y!eqSqUJCRjR<_pcfsrD8dfW2fL;aa5#4&}iY>EJ@~MEt zhabcb?~T#drx#2gaaEjL8esPdZ@99V+qgJG(#sYZL3AbVC%fxN2c7AbfR$a_=|i`- zxnIjjS|H6Zafmj$v5g)(cVUe%HW>i{v#5Ck&U3%1Gk1bLhe3-_L%k*WGP#kn6k-Fh^z@#ug0 zk2{?m&`4m_C^VSfYl`e8EsNZPQC6>T1txiJ3-gn`J@~fPGj()P6^7etPt|cfn_|-@ z@XRUjXyzHc5h?MmipI2?m!CAzBug}Q#j*|CwPaavVPIvX{m_mCo(u$X-20^)_e@U- zGlUB>8GTLj+QnwbCFHV<5`5IO#%qSuCE>R$`?#F}yye!O)l-y0;Zp&m$qR0y8u!=G zPN*F0%y{}tWBN2w3ig&j6s&;46UXru<~Za&+bh3^P4bz9 zgFWrw+`GEy#SzVK*Zw~5K|I!6i2tyOI^-7IzSVMVUL?kP#ct19gBFTJPqfDhO;n1I zt!A5l*uXF?4qYN%&?EQ=vPZWz7DmW-iwGa--SwxE^!)u|*;5=&<3U&fr|FfKxN)09 zOo9H4K5SHtXnhkUtOZUg{ffR3U^d+{if~RvxC@5Gw36Ru^cri!TC@F`02hwJMh=hK zlSicVB88>-wXH8XpSsGtoq%>s*+88E<9>@+Gb* z<`3H$ke$}9*RrdmUPl+XjHUhhbk#zsfqvh?u4a9KD4ixHrhVyl26f8pO|J2^`AVEc z7saM>Vs@_)SU=9S4?sq;Y|Y*AR^A7G7XV6L9)#(wd}x3)Ty|WK&?yt7p#Cq!c@g&a zqe;R{8EZ9ZC7XWt;Lc8Hv9B=k0Cgr`kmXQE$SB1jkPlhp)lb#2*(p^yw$oD0H2YV! zl*S+tG%We4H_=7!vNZl!Wv6m#obx)FWLF#AjY)PZJ*;~8rgbgmru>h51jfeT5rn9x#bQLF5+2GjQ4)#5t z2nPB&hBY&bt^mrB^R?8zLhaML?HWF^J0IYi@Fz3hYOzVg`+`@p6`Y`E813CgVT*JD z5V!5`k`$G#mutf&@LlG<-*AAiX%foWwHoSQ^ogG^s|BAzjX0Wey zB<+M9o7#KL%Y#F5aENSnFGQ{)*n{WqinrfMm31TT*k0E=em!UjQND3(V9%d^u!htJ zH_&n7@s-~k`N@GUT9-_;7%C4MJ!5jn=)Il^HFpDa{wmddLZd|J;&LX?Oh5)&lmM$ zs7Ttsai~OSE#_xyQF?2w6w0?5@Z>48eWwBw0@*jJRihL+ejO;$v#tiT@QSpDgEo@RO!f zIfl0WR8L`F*7n7!%uL$9bgJl%5{pHW?qJ$@JoX#T^^a&JqVVsB)TNl}Ar^)amCfX1 zO0v)EeqO}ByYLa(qAxlq2u{YcIFMDkR3MPNJHmtv9CKG9HUkxpiD&cC3|v7t#TY_7 z;|9E0eT|3`$IAr7k)1WHUP2eu?bs1W3sgcG<;C4 z4UflJ*kqwF6&v-%zUWIteo=*M)yh2pcU#KJkFWd{_MZer`s1H z)c(i9sRQIUS+*W+@DWZL{LEmnj4IbWI&n+#2SD^*PRtIhlJO}BBwcWL>ova*do+&6 z(I2dDPd84}{Moqp`wXU3!Vmag-z18%G+Fq$g2vp5O%NTR604+B@pB)^O^-g88mWon z7(>tkNZ~*9YwGqvbUSiPW1N}UIqK-t(%4`9Ck%rQXY{TS+-`fzC7<)KCQs5Xw@~Tn zfd>e~!$F`hGf{$#4o3Iwt(h=laueXHlw|@*`Qb5>T@#s{o4+UV^H^n)MDCx32&mpeu26>rjU?JYb@?$JpgDhi@3N)MdU5 z5UHeWpCr~)Bl1jnP{q2!^jy@Dd+p z`VW0z2+_1$X(31t@p6cF@xK2beTQtk#&jDO6IfY4(@9Pgsfja!EEtKgwK-j`H9Un%Twf z35K=Vkgo!%6YWp)j-12!_KcjHIK?IO=NXtt{O>JM!TsfgYvFGe z@(3mXpI7%FM??ie|IqLF6NUAG(GPvl1^^4+P6OlOXX_ruX2~~LvQFDfo2kY^dMc@q zCYD4hTmE~iEsMAW*;0|gEBeIhu-_C*XUMUVqw57U-I(X1UY7y{c@3z&NYO}`~q z`@t4vEhzRYf;}@GXj0LT+qiT0Z+4hf2XE2ZnxD0D=mb7b#s-hzu+UHa_OJUC^;ePm zhU^%li<0iMY--I?w(DY-?9pGCxXGgJ~z!=%y zBC&ipWzLI)jF3(puw>|x9sKyo{%i$w-__v;5EZW<)uup!XzRISeWLjwkj}rO3QD6% zLlRhEmoSk;hmnl!l*Ki35f5m@)8Kwa)ry~=f!Bd(fiVt?p@o*l{XWrZt`|Tq(>1{c zAU!Do+9pl%u#lX6#|no1Nr11fT;FClw%K8G<(sw8nzJDe#yiG*Qn7Ahc|_~ulY{Q_ zv}@eaMX8uFVun3bRPicApGiGZil>C5i>|EjF86^Lx$HwF0Ux^xKr?M@C8kMmon#j} zXTm7dmats19w09{p!JA_jlhtPu5qS}sV+?hdEui83qnRbekS()B#q=XLl4RA7y(ovk?H_vPb`dMJfhfyZRSnMqjg+p2^kukmGt|< z5<*1JK^NW0($4uZ%75GlSU!-VvnGMm*yl#iqn&I$lG#ROxND%-8z_ohJ(F-eiB> zrGW-wP^$V?V}Xu(H~?6d&?iv>|C5wmk$A>XcZu3LjftE`IE7oJ7XP}=5CFD2e`Drz zi^<)0fURMMlSuP;*j_KjGX}fs(v*7-rLU5SzN&Y)FI1rquJ7@24t0}A#D?_9PSa+8 z9=l?vdat1s4FC>RB)xIvBH8_y8w6&Z#LUnO{9K8NMi}7vFsw9}T8_oraSWIqTbb)ASWWqa4&hZsy23K3Y$7#9!q zOc7Vw0Q??}za{`NWE7YhfNXq8q-Pvx@fvW1*I*=vi}g95;2B zVY(&fF4F3eJIBXswHgn%A!1F%9g0nj$V930`@$8^-+YKV zzxo{bE!!LwA!!+q9ctOwUkmn4>fu5XeA3Sl)NRJt6pfP|9$$~YzJ$pk^7I_}@=N@u zDMdlmjJ_)Ek9s$tldu1VL>))A$|C!&RbO*~FALesWQsbonFlw)9goEb4 zZfW$_Ev?G`9`@wPUJ%@3JZ^f134kw}YFEX`t z(cLbJzI^S-jYMoOAVn_b=5j(k7@QR9qT@K0=vhN9p&&BIh?2v5;ydP?358>8x6r$g zC?r0S9aZkgYz<7L7E_5O#fHt2>~T4404y{UgRgXjqayzet!;mV4`;>?|BYa2qt-F8 zen>Oor?U27;zkKxDpGPu!0k~1#Z$0egTJ2W)j{RxSUb_Rk{pu@1Z#3+sa>{g2E7dt z0C5G8HW=cdn#7)xI%hOMo@(>FJVhJp)j&UXi0zCqagP%VQa@vW@cmoeA z0_TW&V|xJ{98a?=Ky;iyY$&cBiu8D-T5!5V#KP`vRR_MoOUg9OSHMF8YrNv_Kx)5> zsPR5NuWeG@$N#ubK?s8ge6@z!FwObr6f$-hs4g)1uN$?gG82obNR!u!93ctvTM_3& zqJbSQ>oh^+Ol{&mqAhM15wWfIJXVcy?pOpjwiHUV8c>RIg_XvKg(~=JyAX4T+SZRT zO7V=n)Y!#1XDvSD!FR}%E`D$YHNa3>O>}eh5qOTl{he|M;6_BaW9vl_N-un@0c9W} zS&*IPcyj&@!d)hahFVj(?O8tfghqhob zMVcW>n3yv6#+{_VEl;8eDKkqjIl>%=!rq> zWt(LB(t7P7Z4OAz?Z{L_V9ZC<%uqA~rV>02S$In=enpeO<9Lf1yese(7l9YsgF8RV zTb}@yq9>%@v&V&<%Kh~gMBsB`F4YllM|v+CXdN#aOJCYx7IO<58}}3oUcKzw2{EJ> zcrXCp=m&(@1GN@+%hrQAs+>INucZ~0WRchqvxWiGG|^hE);{8d#V-;JaX0TEO|r*H zEi@C>&_$?S(se$A{Sj#X=lE0nM?ecO)@#?xc1^M`Z8FUAR3fNrAo5Lr3BTDak?@-d zt6)20hCu+Lk{6VHo?1RaYPIa*grbZawim|ToF%%3aG`2J(k~+C?|^St&Ze7AeD~osxxnjt+Mm`H^?jo}Awku5sx-xjLT5<0F84c|!&=Gu$xG@8CwyLcUM^j|g%;hO6>CpJ2aDdzG1ljw zI#-RSEgU!Q*^uW@{<(UfQXGUf7Ap>_X7}5wzpdGF{@%BuJw+;u_JslGXv0)%*WJo^m`@E6U@8fL6BTG;hI5$b&-EWLpF1KDd#RSCE4)2B1$-hKy@YQCQ z`3u!n+s*R$OHZbq#};02_7fURx7Gfm`sU=snL5fInGLpeJTi))Gh~>K^6Y;%863D$ zh_qc%J~T&v7(CY51|@{Rjlo_eSresh!3>kvW85Jz1+L?vGVfi-D=*A%(mOa#x3rc` z?pZwiZa6do>g8jdzoI|eZ=?kt<+=NbVX}vX`_iz?apH@8Wip05-60~K9y)6!!}BJ~ zGVsOp16B!;_=M9Ls}AtCY>tMDfEt1nv85p=s2XQTRdqJsc+ylOk%8}9fW|^nN~6D{ z7R+9l#*00#9sQX0<|Uuk+go6(`<9rNQH%_eAgN(0X>#gt0%Ox zkyx!#H8u0;GmGg{xw|B(_*9*3h~scFh2+(3#(KMI84l1W;r&4AD}D3eAlM-cZXeCC z`LJ;`nkn-eb~Hmqxh{*(AKp&BWq0)>WK(-ON&ueXFH<$N%Gc=puC!(31Xp&3e%zVD z>V7{gMjAD&!D?kNCCTy57G-ao+Lz%gUpkPhLJ1Sl-=8p*J#V z6YiV-)r$DW^W?qd-#svrL>|>W7)GeZ*3-9)oc>V@j;uKhM*9Qte&GSn;U-&Md1X;o z3|pO=a6`XkGj>0{I9UA}cAQl|CgA>4IqNx_E6=901Fvx&z$cn*S(?lI9HnVp?IG*J zX^+4~A~I(m);nTbLV=b%{KSxt2F+f4i}4vfnaoC6CejE7UN&?o>QF*E_HCx&j?L7! zte!lbs!e+*nqm?PwDYA@NHy*vu8bhdj9+Ui0}ZEJi8VvY=R)caeQq;4T?v0dZ?t>^ zh_tVg(UYw<;Q}yVxpUrHYuO{KDy-y>U@RLFZ_kv@7n1~7M=khb@&{!c+9RYp6zoF z>4D^&aj83+7*A%-qikUcd2GS6DIQl^jP5RH-k0>f)XteI9g`sq>bx>H_UOGP z)EMnA^phO^B{*qco@009w<{5tY7VkvafeP~84SSm|MSnpjiz^{ku()+g7$M!1na_N z9?Wtfw%54j@w|yg87*DUY*L3m!Cos@!=z7xU`id5+m2174&g-pki`mt|M~o=ilN>+ zr*5BqCtxz!D$i>9UTeF*P+A{@roC83jdCr1yhQrY-}2KiNs*?~i;mR3LTgT&|MeFC z%ccJ3f8FDD;a5${+T^dwCE!;zfry~&;frun#sFm1$JFlbDxtK__gFrxI<8@L z8~YbVhqKO485-ZQa@Pr^f!`i%RUYwa73eN28mR^!=pueVnILpETI{I3*=_nAc_wuP zT?krVjYUKsv%?QbHc4$O#wuVRVZQ}NM_b;$hM^p{)0w|Jp4#nx{-#1R=l;1(g#v+V zYa7f(#Vd}BgRSUhY7u>*$;u1P{|%;y@Yb_yA}r8TVy1dzl=?{kB@}q{ALNtm$Xta` zgR%tuW)jd0Xv=|4%(;q2@0o3(c*OA7f6klp3RJT_yq!jAS^akvb=e-n6NxpsNEzv~pR3?nYQ0oi3Uz*g# z1ct>}$5rjxTZgV2^(@@MYR*25lYXw7cx%RUM`pHTI1w9dwl|tTxeh>$)X=SHB!sad zNznCd)Fm(ATm`y7S&S^`d-qD7UF7;xELY+=VRxgt43m`{q~x*Jhj+@s^3L0{%K_=| z$t1<%q8B%T)`&0%9T{1hnP_x0ZgdZ}r?p9 z2OU?M4ZMzrH&~lrqyF99^G(Vh*@An!kPo->14Q0$^2vS%U2QV)r|c-&g`4auBIl9T z-{3YBtJ(>DKJ8WN+;A?Q#ygRIA_JhMDOv|VZ$7IB%JTYbbes;VZes(^?3S=ddLK@k%6k{SkPRif3oPER={j--*ls<93o^}6D z5FJK60iMnvz&OMG!&C3h{ds>;-*DNsz?wZ=u}RjH%``%`V;xJW5gyoa&VEi`qv3ey z+}Vi?;fKfL@`O!UgqMd8p=h~K=Pr%$4=?WyKV;iBYk{81^@KC-_@#svoAv8dYH#S; z=n;u_UQ)cs!cofO2ZE+@62G4gYnj_SbqQ8+=;^7})64r`DCfm|)k^)hIwR%hyimV- z$%H(FGEo7=qUF>*kI`svVi*fZE$0*Jo=1*fE}}7Jf4_U7(xYFykEeV7RblV9ILduA z1;_(Hy$0`BVj>#(d-$j5&U-$oD|}+2+UV4G35+8nv_Ase%0O?UpeH`%@ljl!taBx= zpIjl#=2;GC{dvWZ#|OC^`=_IJ5n+AK`m-XS4vLL_ZK3HF<)8kE14*T8LCcW|mg1*d z3~I7y=~BL@_qqQRo%_2`)PdBm%GcXJ{Yt|>U+NQB-d{qRlyd6U-1J19q*UKCpsjph z@W{g0^&T;)H)B%4>R+g)-CO7wFX+N;{zKtw>CXgO@L5Q`eRJrkq(aZgDwQ(w?#X@d zWsf&rC`yze-{P~0!Pxkehl{8N>WJxhnb$Tg&+AuAph-TPp1RY3hx5CKgvAw~3gd>N z6Pq1Q*$Ql;UZTp+`%=;5r)WA|m6QnzA~r!{2g~Ke0t-LJ+|oD*HGF6vuGlA%kzdxb zOX0Zxpy*YpnH;h$fXq0^4iW@*=GGr%EFa`h6-cziKIIMmz5C}C zxl(cn&NhQjW0yU?NecbAg9|dWIczVXR(!sEri=^nHF|$)UOyxflahPWMp;P&Bw&dn zk8oXJz9Xp1Qgb#9XPZgkXRZm_y>7dt+qW|f%YK_e4fOg!)6D7~RFcb=ceC!NXrUj4 zpH%gedL>?@NnvE(Zi|Cm0L|7}2wSH#Xl={Zk)|^WK$#ac-Qzst&U(t@n`A%^+5HMj zHv8b<4mhWj*+Q=-OYX;}0;oWKzNj%5EhlNvI_*WSoWxiI$}yhS1X_(Fe_#NbgSxB*rxX6;9Rq-s`Gc#25; za+iQ05Y0FKBP`^x+aGJmlqGp9YcX;DQy*IRH>*E+CQ6E!M&v~Eqncga-=YOJToVuW zVEZ(=p?>Nn8JX(aBkUQ9*J*tzjSaj>J8B3jufI+BE6~?}ILtGz`2~_1GmJNy%zQ@w zw3q4Q;^6R}^-#fH_Vq<-pJy*#(Z*(_4;f(lu(Z_=wfO@1jYCy*bH-{uU$C+l+bgzM z_?3Gl!XA@L^lh)VQ3cJ`Zqpi}KEQ=Cto}rOwPfVb>6-;Dc`sKV2U+9LD|-Dy6s|v{ zK->EHQeE+HMdx^Rj3qz4iVHu;CyQQXUQ5_0g`DN(6yNH27O4tiqrE9t(PvL3myJSIHVxQanrJc>GcffLndb2RF zD504=9P=54-{otMhyXRySMXERq)sKK4IrJFuq%Dy&NuApPf_PTVGgoeN>)U8N_FL^ zNOhxquitNS+Xps6-&*LD0tzlg&|T6II_e!Ibam=@7H;F0rDOd+2+UE$V>imYOZ-qg zpGz{a20CeatzTR-4}N(h5>+*&$L+g;q|@ipI)^>8g(5w z6yfU)FfQ=JvA{2iB{Myzn6sBG?{bu@D<9BQZNE&xyE2G9vVTY{h}`Z{lxzP3F{DWq zZ(I}03hInkL02hM0C@Fd7S+qhW|1ko23jFNUbif>PF zh2;De)0fKi&*+(mC#Ya?KoBCgKov~?`}GF#V=n!l)@aVV((f<-o`xnE_Vd&ZZQ(pv zI$g<)qwOF@a&KijS_^U#{l>*1dgSShpbnhKQ=7^R!F#zdiu_Cs{bdfmb5EB*9_B&Zyz9Q8R}BUmc} z$@wbd7ncPzDna+R%;yk-!EA7tJ~0l=t-{Orm-ilZSt_<`5WK;corzea_+21gGniCD zL_t?z{3(lp@#V+n+USXFd$a6LN)b?U!?L45&3Q$yC^499t0@winazF^Eu#~3%SSBs zHYi4Eq@a%CI(Dv&I^uXaq&(RK)oXB4?K{Nr{v z!+4$b!HSpqQCg2BZu1F+g{OE?a>(mj zU~(Zqa4&3b$c^KspTHdUr)ZmG?yhJ?Cu74XWE)sxpAp8}MBq@>FJk7p-tP&qq>^8# z5d(uFH|ah7ejZtMui7_3jW5S8^21``KKlKaWhaubj2i6$*ZtFfu<0J9_w>Zi97N(a zDKRM=cGE=$0Tjl;tt8F-a@`ec*HU}rT*z5bR@tHA5<=igZk_O_zNc4^SNyLGz7Zqs z;B#H#H;wklDCmC3B2(5oUT;Mc2|?Y?2Mwo2hB0XcT{*=# zmY_;{c`4wL?%QD~dpfU$9UMuZ$GeA>ePCt^w+pdD7`UiD%PG!|e7sMUcj>Vc7!F#D zD0meXYYj#YH0r|+$9{@Vzi;Vlz6#Dj zdKCr<%pn~Xe~Lc&!7NUn--RLG^e+S)h8p`bJyMB(_4K0Sk_^)0$y(f#v)R>4LxO=r zxe3Vo1`W!&`+9bW$FACI_voW6O@%+hu#i)MkY_aC}FZV_R!*0 z+jc8DOFjI(oY?S6jS}m(r5yipb*fIl+@!-mzEx-f6s4q;C!aJ*ggWR`&W#{z!-Vzq_k5FdCHZO*knByPbXV82k2O|Dt*4l;s3 zgI^K7HT4wiSXn7f=0+{2w7aE2D~AOh3uvO?*Md>jS4pLLU51L(&O8&70~q+m0a=?M9~#XrdTw- zxuFMn<8Q4Ial7^PNoS6ZNt43Eg2lzDDM7Xe<@EWZ#FzpcYG^q5N-Ooo-I|9&_eX4~ z(Ri_4*lqfqjkDaGo9fc6^~w9aVgO2zCW@{ZK8Cq9Ru2)i54W(n8Xv=fpHdG*I8bkm z=MuG8B(v=sc@Pw&x;1_hpUDA&p>n>!@|0HmJQ#uNzpUE&8Z{177#QOfC#z+M?7vJs zEbquaNU{0wr)Zy4UcXqzN8B>mMMoAbLvIfEF9sl7G|8u0L^|{OTKK2CWT~h27_8kI z(Jdn}x_tX`WuIA7CQ0ubVmt4v!b)PPQp96iX*mBEyN!%gVXQ_EvQ^bB$Q@t>fjNYm^6yAt9&NoxO)h z|FUG3@+-+dRCrLLjAR$^G3s`n9IVOOoRS7-IJ3lMu-lq`YEO05Lz(d#v)eY*t0`bV z3NT{HmWIKZ$X_Isc3I-(M;Y>$OdLaE!En-def&Fdc)4MJK}Q36-)5tvT6|d>jhojf z4CbzsNm6V}!ucjqNH(jZWfTKYi}7JQ8~%lFJ^^m`?VwE&fwWyGDX6qo7mY9M_eV&U zIjQ(M05y8Je#9EaUESu-k$BH|<>j_O5Gc!6T4E_??=GZ(8z^VcPHas##iuRB7U7=p1IPP6MTZ;~<|GhlrgHWgxdy2{q2t%B?uk2G z+{(&Fv)?pP%2Hn}mwUg9@1vf)-}u2MilM3eZL{#OzHqiTmu8^MO~X�c2az(a#aPCLg^wChDlCt;NFQQ|c*vc?}$j{Tm7!kZ{r+t!l5E^ueQUhz}A&xB99(r>d%1vX+` zG$srmap;(fj`7zrzTHZHgdGNbyEtY@>YCmxO9a!{6$M=|%i>^q#L%WLjPs=zdI-Mf z&bBGxM-|1VpqoYfUela^W4F2W$Yf{^;>0H$UK-#1sr2E*i|RP1c~%?K+a`M${nYTk z;jDY(f{lUszukNt2F94CxQ?Z_KSe!gonqQ?k^z)Ko~d}196@tlV{3yw1F#gGy2?{v zd@?v3$YBgY@9j;w=Hi^7rA7go6@hz`pZVu$@k8Vu}KC--|>%(gp$Hj#etPd>%yY`3YAUy@3N-b zz5M;1!dL}j{N{ACcc3uD5mT0P6b!v2iveU#7kDk*H($(D!_CIb2vntVP|v+ zEavnOp}7^K3t$Va7?Z*x)TSiVD61G>P!uG=RG<5%>3v(g|F9xC!=gJoiWjKa<2h$c zDawa$(a3e2MnIA+vCBeCYmQ=etSN)#F^_Eb@UXr|ks*EHND8*U!FXaQ3e z5HAQ8E zJV_BRf?|#%`&$LE6wgL%2T;i(e1ENYKo| zX&-dJTltf^h`?|1aW1~m{YphNVEqeLv-LI<3A%t32saoqBz90Z+y-BE5qFf=A&oWD z7LK*lu(rHBVSo`0Lh!@OAo)n*(n>joU`b(|Ej323|58#Pb4){nF(R;m3ryf3SBN|- zTORGmy7-WosOh*#`EvV71%Qf>yF{L^uJF@V-sOVDtp`QjDkYG*1m|^)k{jYXS)r@;diAyy^Gy41${CdA@QQ1F# zJO^r1)T4{>jf=EcpoQE8SztcbzNIa3e zGUTJ|qa*sDaG#WRv&*va(|ys5cSGt_t{A#DYhX-oegaZ4fi`65>>^rcy0@>)){z}> zGF|*gP&CIFs8n_LIYV?k1PCr1@X{;R8fLq#0%Bxu8cG}*?iJ_8-??(}UQvy+oVlDk z=w6I4>~w8`W7@Oh{11v(FWEXO`;z-5*aNaRf4j*74+dt3HaT=Jd=J#%6$#`?4nP*l zvWCRG(G?@6a^E~bVcO{=bxKgUaxG>WxZ?z_A8Q)oYBv39PHeX&<>)a!tw z$WF52woYMNe1>TJ!g8nP%wwm*;e(u&8$;Th>Us%vT;cQ>r9Tikkba4Su_E+DUUgw9 zd&9(|q8}5iA?P=9s(`qA6laZ@nxPdx=Us4Wvf;L!UWk|-i+&*ooR=~c_v5j@Y_MwEW-Z$^XJNkM>eCRB67S!j z8}v-=btc6cB0k*o;YtI3v9|R@t-pbp8R(Pd@RkPeD}Zo=viSkx8GvR$j!id zMtWPjli)r2xusOsn*3rmS1m_*y+D30WzDSM9byE_f{qJ4PR zN7M}TEOvQ}#m>%WN+yh2UK_Mtk0W!%f3+M)Hx!q=P$#ar}=RZ3oRXs;5-U% zmLBpJ%~;!jUA5;I0hQy@$D4}ZVq#0r7G_Hj!$uYZ>7zCT(%Arcr*i{7X5(hWp1RRm zw~bfV3*vM~%kl7O)O9OG>RYs+k$0*6u#H#9tvc?#)y0C9bgOdX{Nfjjo;cUagexXdTW3_d?d@gJjNG{^7xE`H2~F5>Y^#ypthx1$ljr+4s(aoJj?$k!O3Pe( zHZIIcTad2SK3bHmx+k0g#sb#Vx2`KAdnYUdyr)}At-1Bv?sJ_`j(AbEzTAPx8TaN* zPNo)3ywHqD_jnHykW30m8J^okDb+O>*Onw+R4)uPLd3#SdADkPRF#B+SAttiCY;sYwbKYFUP2}us zcU{dcxvF`4U*K}zX1#g?Wc2oe*FyL}}e9@mMl?JcI?W-Pex{?$e& z@`*IZ#zUr z-2l!xqn_^bZC2UjoH&>|*IO!l4U;h8teEE-A|?lUoxHW}I>g1<;5t8uRKpKk9c{NT z;JSOvdJ^uHJ!GTkdi4vfo4~Bv_5?d*g|de^ghViMrTEpO!*=$H%T`08%QD$s;*I$~ zLTCxDH31E*`c-TqwLSMQM0bTivqM(Z5`I^c59T2b_N@w1>@fLWbr|efyMMr%yxJsq zh08aE>g!K}wKAaGkf?JJO|{3*KmUfSz*1WRC%>Lvd22s)9~|H#v=%&VC)YjDocJSh zS^ZsWiaf@)#7SYdW!e5)OP1U}w=~$6Cf_-m4>RTdxp8ujW4F^zI*L@@At8UI*h{B+ zDQEnWh`YdS0B^efOO;QM78jp|9V`k4F_Bpj+O2OK3B%*qc^VNcdqWb-Pei zHpnBxJ&bYfAi3_&MkSMeTYrYMXOeEm>!_<@+->~3DP|EqJ@%0|;Q@PGoT25m^o;PC*x09q zK3%5PKYST=mD3}8NoPHWb(?02ybSjJDf!|p`u~~*`1m1=-IqFObPYc;aIgJwolf;y z$EFT7Z>#{nRsOFEmzlzM4UBA7m%c9AZX7{Fb;B4FI{%7DSAtmY+lGdOofJP}& z%R!^EUHQ@iVdN4oV=EY< znc;g*jAtr|Y3Gz5?B>eT)6+j6^Ma>Cz>l#)lkW`s+CkPoiD~Y^y>}>#5T+j4JpY@& zq^3wVAYnBWV}aPfDViMP8=_Jy^HQ9nFdq(I&TePv)aO0<@K$s1<;)(`Lo%CK|8c5L zsB1<=Ub4f*6x=`(c9~&hJCG2aTEWHIdw?B;zn?QEeB{INJhaqS;5+HZzISK$LI*=s zCP?%+eK`j*=;NsL8uU7=u^rISSAfH^HblHnxOUfJ;FV2@Bjv+I1_#gcE6+Yr85@Y% zi{9ass_&!98_;(q;em%g@}F1`;VV8@Ja^XFFttJ+Sb zyUCbQ)%VDGW{<+C z@#@8+Vu_!t8>ni~Q+`bmeI{EDDfR@Y`}IJIbJ^)z0Wh(7sVkmti|enkuTkQ6c%h$X zxYwC%J5DoyP_JwlsXqn1-9ye=Mv9)icM1S)D{HoExiW8C?4EwEqTY$+S21bQi|x-? zGUCo=0^TN=u_XU2=sOo_5b(6Z&s8hSwC^~CI1;i^t++fLm0uiB|163U46UN0ym3|b z%%{zmJm0$z!=e6p@t6#Xp48U*H?}2Oi#_|8Wc`#07sb?`{VT%92mGS1KgnX5t)o?| z>f(ONEx==;->lEn*r(lfyDm6Duded{{6lNYi@vT0i_%ldFh6|E8)?#%kOD4d%FQnD z@5S~-CPI(?TjaP#eT8#CS~-I~<{R;&_h=(xgH+{U+cv;C!7bDmdurY!>&O1RMaZs-F}c~XyuH`SKe#xrs}%ivfWxetEs~~bzW>pJf>x}r*8f(eMu;7 z!g=a`OG5tPm<-0N1i<8|4tVrboHJug24&CihN7wZ(@}DiDQY|BqoSz2u2Q)Go;m%` zQgFpy(T)E1*VZI8fprWWNO=S6DE@05cKHRlA4)Yvv+XT*L;C!X7IvBr*ZA;TaoczDcuAbI{w3#`C(-$D}Rkq(mL?&&SrMFo(xVxWQTdA5M4=^(8 zTtrG`Ks~F9bHXRNUoEyR!$O)%Ng!0;Z_$fA9IJUll$l-+7gkYm(T9B#+4_}CZcqtA zUv~KlGzsnv<7(5n*9@6@7?^ql{SZbfh`wB_3t+TsP#p^+I1-}n&4SWDH$>|z*JYvq zFYuK59A&Y#bX~9ArH<*j|2^7O)6Zcp&;VVFWbO2YJB-rGbDVJrE7DkMtdf?cDy2o& zSV~a@-9G&$cQ>`ZP9391M&-WzW+dT@ak@`(ZBLq0*_;|o4$dtkCxf|`*{l7+i{|QH zhoZxTpjv=zdXK55<>^%i-io?Ezl!d4IyBh)-9ALr{LC{U-*V}1w^hnHiiSFN=C}-@DV}s&Q0FHaldx zOzXv+j1jFDYc#7i!M|D5s^RH97^h=B7CztWp|6mn{7wxyKY--inJP$2)2sJb)IKn# z4-9hE8$h^l6AOdRWP-)ts3Fgx5%ep+-izI_^|W5GlKM{jzE%n3P>B*~Iy7(2->O$cL`?Ad0Lec#Jivc%YhAq=Br56{u(yFJhK`#sn7 z`~Nq8%{BLZ&ig*+yw25kO5=Dr-{ zO|#`TZ|9_t5dIrlr&pGQ3{B$-Q^&~lg@s2^_==qQOa}IhKMm*6cdG5lbNhT-J?j+P zD;-?n@2j=K!R8R9gJ*HM6R~1GXtoHa2)_FKqqlSHYq?;_#(uGTy2Y&09i&0KVRJ~a zyGp1KFUQgdvIsJ1KC49FUA-(YaPBSc73LCIAX_}|({Oc7n|tK^yh;%>(K9D|v6xm2&e@l^49#s{_Wm z^g~o!)oOXx-lvE3VYn}2)ar>rX4<`4r;j?gKSktO``gg48gq}Uur2$85TUaxf>?u6 z%dq9JieX*SYxykt&SY^T$FEmD^tkcW*GpG6Y;J7S?2HbYsroz&$kb|Y=`oBqa87h+ zifO7%or@kx##lHp*-)-y?76lWzX)2C9JLMCP}anh3I?tWK~tW>X4r~W-B21nK1CL2 zR2kJ6_s5lcqj({ukDDV4)Eq{{iHs}7W_i;YtpacsX$GQ@A1`V+;%q@@xFR1 zv-XSD9E>jQLg(Win?_k2iEpu}UE%6PKo)MCEe@cS<8?fp(r>QTQF+=?=FABWF?eGa zCgOJq2F)SFTZ@0c`6~NropdFek6;Odd}Rf`4*U{6v;c#Lq4h$>t18N0_nA~N$HbXO zlqbCsn+QEFoQsK(IUZII@EoFx_6h~%%sqVq0{6#xYCjW0E!>Pq@S?%G(iZ3NY}@lV zdPkWsqbf)|gkwq9Gvnw_WF_cCwHgy&yR~qJN*NkYe0kdLSr-kpYy)8gWE67tnLUHt z+g(<+y4|5PdxmIHbURc_Hj4v`x=Z8nDjX_Y$9~7dbC#Zk_tDwF0VU2aMrQI*K_u5)+P*JVi1(>N3Zjd;R3>l3A%t zr_SbrEjM?mHTQ+d<;wT1-{EV6ZgKP* z2@XsCC`Z>BJyT40o8t4w<6r?PAg2t*=ezlzkg=anu|0TB!k4rghqciJ|EHaWWcbGK z6rF+&acf37tKJLVe=2RJUKo1+@i?Lf=45TyKVP2;{QN9f_}2j#!iLRfi<>)?mhd2n zZM<$l$0@iTbe%;lG=)C()G^Eb>9Bw!cJ)E+77vfm?)>9*RpmWm`#Y5e4F&lYay{4J z7ZmF|11c{ML-%*>F2zCiUHFfTKRh>Hx!i+`It=*f!=FH?{Jleo%nFqK4woSZk$zjuQxi+ACRn*#M7zCjAXTO5lYmOn+dJvEtm zupB@!0prq9k$jjwdq$fB6A@K1ZL&c7fVbbw?i)2*j6qtMyZH#rX@6?Cf*a=aF#C&M z=d*=p#~^ajC+AK8j!&+HgvuYGddAO2G#l*s*p)EZsI8D##<|#*2&!}2Iy==nlfJAD z9~)aKSl8o%nY-pYI;?MJlbNw}J00=RsJw42xwJmPa#0YKhg_Z&W zOPhS1R;K4R=AS0mt7iLsv&%e2{Zpi-Y_g=&Qm-+S4g|sK5G%1%=mx0s|*X3K&&Ae*3}c0eF3F_co2LE1VlYe%(SxR z`T6*2LAZ(sd1LzMAwZZ&MQ2Gs#Woo3l}dD7Tw#o3XA622xfo~HsO=2VgTGw1ds=tM}PbcEJ-rQOBP zitVSUR!$3+V_9%4JQJtjd;nM3Od`yi-h5R|J2fcY>W2e+lyc&Jhb3P}m#8zHFHs6J zQ4c~H9KmR>%jkdRNTy>PY1epG=yH(Qa+O(oYB~F!!KO2G@V+-V^TR<<`(;*tZe4|i zrGLb+(;F;TQ2Y)D+jLA@RC6hCl?;AY$U9VSxUA80x$l)qohRg+98Zg>3dI&i5buy! zT|c43zd~W?43CQfz0l^d7H!H+vz8|(!9Y}B_#Iy@?Vwf|E^9UjC3|$Fqg`4b-{k(% zf2+tsh4wBIa|$raNhi0l%W#;&gkr*svUvJR9Sz%aqYg2YT`lvgCBvz}@bDJHB-?Zzz;_(V6w|=q53xZNPJWH=uXAxW;Bvwx&@-^I; z%^{md7KJRG!zHf$WKnBtel$a0#LTX_fSF z9$Y+z+T}Dg8G?^)s}SFXmQeSI`77O5>siF+MmR-bLW(J&%n~lMj*8+>s&&_l5^rZ5GMaj5pV2r&<7N5^H3z?aMD;{guzLu7rzQ1598P7a$4MNko2aR%A%?Hm{T4f1$x5*2 zLDBy;VK;=q9(FfFxhibA&jcmEx`F@WMZa<)Wmmb*aWp&co#J26tyIz&dp|j?@Gf|> zr)i8-!#;d!YaVqvh4r3Y=d%3Jp5{TrYd;Wu`_$l?MTv_Y<`&|G6=!d1ZMWnX19p4# zgkhbN)BxD6yunMbs89i^dD(2mLkN9<%JsNtr@1sqz=Cw+DT&tu^=Au($>- zB23RG9tVBVc#4m1>*SQ_fKm?Z;r-g*zx>HUO%i4q|LC@j*_l%K51Fd?eJX#dCVbLc zn(8y-FBrK?#wtG<+2$K6#ha_#AJ{8#J}`0bT&bidkW_u>Vl%S>O`A$zWF&m*wX)vz ztqyjt53Z-BdYZ!b7;s)0K#oHs3V9+>ACSV=RuyK-p+=kY8I| zacWMVzy2)~xTuqIGBuiAk=*OgTrqaynPlQC;@kT%Lz6Ed8+iawmP*KOmnKgsdrRO#OWRBC#Lr+BWzcfbNk3KokWB zB%ZF66{5uF6!{#nj`cKb1RhX9;kvf?UJnTGHZRR(juV(N8jhzAgCbME0#d3k#65c&@hM zlZIe>F3&~`dE6M5p3I12`5{WV>5b!hWh#?Dj5zTW>kfOnlb#RU=mFZnFPraK8|EkW zYNP4|HNkF_Bzv2FlI|Y;WX;_Uq+%;9Ix6)gWU){TzO4sWA*ACdzOwHhoWz|^`54^h3~|c*pX{#klV@|mD#q;TWJ!7){`p_SJF*>d2inV z(5^UHd)QCY7TVAJ!uwiV1Emx9Dp>kK5<&iJiP<}|^lyXU_Yl)fdBa1F>}Z0hzrzHN zkMxI+h|S{yA-hNnsPDlf71d5gey~fL8_he*2UZ-$?le?m^81^N4mVoz?d#bEO&omcY|_sj}^Rajs(#ZVreP~kQMpx$WaH8$a5K ze+8n+e`^%)0|roJ^bRnQ<8jgNYQtI{drfR|;$ldobBh&Qg!#GmTVk`R=bp&P&3TH; zG(@@~sGnnLMH3*f&x%|z;FW58ZJ3oi;1R?+=mYL_yuD?Y|Exld*>4haej*9FjlrRs6h9ozIqz1iPuKc{p2WS>cc^XN@_X7JytnX zjS+$tV7ZDHmLO5$dSMWUHr-tRqjP^0uTMVDCv{#m>H;TAabS-XWpF+N;MkdfV&d!Ssk(F=D z?!hcqKPnjpz9w$_YKDx{R~OZweZh-SlZ!Cs3(#&X%3pW9z*_(}exH8wLx@(wrk;oU zGOt5LLwTClS(mJxr)!62U4%VsdczYJRdoh9$+IS98YcEUo2iM*=c(`UrdPk4btXN9 z4M7Vl&cQ+{#hx(t*HnowZb(HOOm^qOf}cJ+M=J5W-|(z`eD9h#_9%CDH8oWGhq1G; zIM(|*Udg@pI*KZx?}OOJkb9Yw{dww(qh`9^Bz0)())G75tv$CJXr>H+xQN539eewP zx)7Uc4-lJpub3ZP(k5Y)qP3*ua!%1;b46VsHt7cb?ID3!lvSYcaz{s2tKsnp3ER%~ z3uy=uLx#;H!DlwMB}3Xhq3ktB?SM*E?sj&Wc36ISn*D|7h!VN0AS%F&6dJ}C{bI>} z#DPy548tW2-Ld`12}4tmm@EcB%Eyo7&8dyb*~wOp`>KoYi}?-Fui;oIZrWNk0N1WS zJP;6q)>NR;jIGl&6zI2XjY{jzH6-PxC~FtSuMe2zOM3~aRsG45eL^%-Oo}nSsQ36g zBi_%4DdopKwMQ5CZPU6Qljk#%Z{rTe!+Y|f>_Li6g+#*+Q5`0)`=e43-_8%D{0lqv zc5P!HSf@bal?ukzlcfI^9PH*iWwb9FC*P?L;A^O-YC+q z4FJBYMjvakI-ENz5Pzz*3OexDS^P)n!uki{BqKt~AdTJZIsuru$=PWYsB~ zNHf9UTlrtDR4MCN&4nsoH?9>QnF2kBeUaukw!i|ftt-!6{b%fLfmflAtOm5jSJ7S1 zau+R*-5;vzA%ICBN)9Fcngoq~3`O&KovQ69B1pkiR{q%iIS#>C&B>u$rO^k5Be%KP zOt99FFF=|;b>*%o)k&LU<>^x-;=O}BE?(CxPfgAi?#8~oy{jGnH9k?i6El)hPgC$u zl}c4V;D?AoH1Uhy>0^Pa6wJ|f4Nz3nKLRg3Tk`FLHa)8Dx#;2gII>u?&uQf=njK$3bAz z0G{`GBOzJ(wy2Exn}FA77w#)V|I2+Gy| zEoZK+vO(f32riMen2aw%4UpUGY&(@ z6h3oozZjGhIcAr{WxM)Iswi#9L10)&d90nYh&`eU6TetAtU)VJ@A%eogH(5hKzhhq zQOsUL8lxkSGyuT{YX}y;H^ljR8)0jB#<#(8QLkT|yl0;Pf{Ljct2=R%FZ?nVm7K<5 zSexm-=VSibw^lvN3CNcaczCQ+{ChuMs8MeU*{p z=f3x)%P~E2vv{=+McmRVcAh5TRyjjPBqWa4uKJ`5_sX%j0IbnCKm zL!+%>c)!L@hkcQxP#{i)X!NZ+7aCE-!@FRqvWj!Y2^Rvp>5LEgc~ZB175STyyDWLD zg~2Xf{uc-&eqi^7tzhBhR9l4$guG6tKkf8xi!dkE>x;G{s(feE?>xnGu1K!AVOj}p zPNAEZoI2cNgih;+@-;1-_}rsLre9$-&Q!~$kK7>5dpF#pw{UoW@5@sfFQbpk^ACw0 zuIa$-4fs}CLpqkG0u^c)_E~-h-%S=^+UW7x0bbq16?k=lYc>t3sTxsdb$+ZZ^S;t# zRbMbCL&CG#!R6!C*??26t?p9+*ccJQel7h~)1U4MM~ z!R!0rkz?2A$FpJ|44PwvzMhSFJ`o|bL4V6)@hk|MZMn2z+RN%`9A4Z*lW8e8ulRh& zPMI$fL=2A0t^6!}^i5XdYx+(3k!sc}HiLm@sQK4fuGnU#_UXXCluke*{rL5*WpFwa zp)9mwzG)K|xn+;J7cU#QSAg^dQtvRthB5^(2O*GDdY}Jr4{u)mmm1WZgp3mg3S%Gi z17^sBbx5+MobE3>|5DSg&apG^orwN$9f69L!%T|FCavl>^qBt0)6&WJxyNdmtYg$g znO%-+C#$1`8W=f((`R|Zgw%M=^S5Rvr#qcQdU%q`_+HtiqjrH`-548=it@2ULf&b)zQR=FHK0+NCvLi0t43>YY&r1U|Er5WaZ=L zh^H)gf^mZp@CeFd%FXjXxRQS!md^`!-~K7E^)%{J2z$+$*x{>&5x4Unxu~xrs$iLjBZu( zgHxNmn=DsuZCiIvJf8~W>~8&~_yrc7P%WG1Tc9bjkm)^lpun|1wFYXlW^ol;x1ii) zSg@ACKWl&d7`sLe9((RVn&Y+nw$OLwc`(V*8$HB}#P~fRO)Ux%Dh_2Z*}sX28u=N_hV~rmfKAYy?D;+KWV9mcgeSj z-DH6WA}V&uEs6>6g{G*eeAo*=A`Iwyu!AZ0ZkaSb(Tq3x@Pew~fDXfc?8(Xi_NG`wC$W7hP;H)_412f)3BMu+^f+KuHhMuft7Fzw zI-fLH3#QHuAP+R_A0veAbf1n~usEq5pKD8Dd}>fT6|BXP(ULwC8K)~Bu%E?VV<7mt zdrANKiOHZ;1Y6Acw3l6Dn+S$gtFLY!V?JK%z!V2;0lZ{7&Ef%kk&&eV2NfuBe1CbU zk%)4fDF}xFP2ErnrY&2{-j5RBqZU?YX8E@tE#9O{Z;8c091ZSpXx&bvGTtEl*2`kf z(YATiy9-*N$?-#*eTyocmd_P)nf7~q-8I>b`Z`l0%tH6z6zuN6*6C&0P8p7Jf=kay z%k1j6cU{1qWp0Cgqr}#vb4NO{i_sCa%ki3h8wjy_*Q*Nqf?uOQQa3&CdA7l^A zHU21S_KJi$1A<%tW%d8LFA|y(25I{suhJkXL)ivP#5;qi(IIJP-A^1ny>@S9>$@L) zCPjN(L{wdPMFHVBfv>;KKgW8(RfN6h zq$6+lpRAcw;sv3CC-e~m)Nn)qAF)|6ArbP@@683gRg@a76rJZOpRRny#>3SJzc2}e zzRMljoLyvBrbl_sU8$(eZ;D(Q4BMtV){)3Nv#2kaKsDWaGJ+xQYt#xJX~kxUUD| z>X&{h(cQ2UAAe2s@UHN<$bPK{YuEr-`|D({B3A@feIZUCfbG))Rpp6k5UtG=0tc3u zeKSE=Yn1K6aQToT#znldVGxLIhkVGrT3&t6E>Ez)pGySW)aOFYLq8(^681yDE#h&$ zkwD(`*;M<2SvQw>S~=XW^i?Xt;X@^&`VW8yGZ#UTqv)vW>^>yti)`T94wv=$lHz?Hf`HBkX4huW;~Ez<8OMe^7~0ISSHwON)13Y{Kg{>S&f)p3W|5 zCrd#`uC7#=g9J%&J4=kD%1c6EL7J3qhm(@r@9I+!_ zbOSl-I`^6U(!(x4Kcs_7g6HbccB2O`(B#*LX1rC>#s4$5MhVL_q$o? z*`~5qdgZ{^&jH5E=j=;5hT>}=*0j2R!o$4YcwCGaOG4*WSE9t(--N(xeR(g4Tp}e$ z-Drlir2hbco7`QbtvhtrEKyh1K@(?0{?rdvOkKBY?= z3oA=`Grj&8z19YvwR=qsP^-`RB*QbuljU@MhUJ@CWyWP$J7oabGd*P&>%aOcZYo0d z)1QF=|9eokAE;Z+&VJ_BjDFhOljL*u`57;JIC;lUC8qP%56ccgVG%#!qb!ctFi*OH ztVGdkLrX2g8eFkGg$K+`JhqfP(luDOrp2}%t-G>Nr*_@bk z|M6I-e~q}=w+6Q0T&2EYN_C2^FC%(#*6uYL=R^1(LJK)pp2S2Gh)+8kd0y?B&gNgR zz@9^ymcthb^!jAm!f8K7u5F;@Wi@w5IyuBK+Z*;LiaKZ00j-~r4Ro>pZga~?J~LLH zLxE8N#7AjOF_0p85bVvWCZ=_QO^boc^;uhHhCoA#DBDFj$ENYXYt2Dn{8!F;h&^Or{{GDT@G+^+v3LL5m#6wV;JqAUt*V zcs+~a9)6*^0MS&J)hUh=Hj3H-I-f_8Zol{0Zx*%lIvb=Ri3vBJ7EzjTH}>8nQC$;$ zFgWZ5yZPN1x^D&X$B}f_MZ=E7)z^ND55re1?iT1rZIH5OXvsdRBQREn>{-Q)%2dRc z2!OnZA#gGP=)~x5PFN4Z_jU~J-bwGSA0!rXt?DSaHx+c4R`YWZ`4Fbu%#KOOMCEcH zTg%+Xh1L>b(M$z{as59;vN8s7ltVz9+0Vg93ZEK$p_~8vy<5fkG?{wd7sqzGF2S=V z!*yGPHVyJb(m;t)MWRRJSwe^=>jJ@anOCC(c+;a}5v)GS0ZJXP12fE(m*tF}6rgx@ zU8RPtCAL|vARO=K(Mz5xC*0KMIhc$hS%d8zW?a$c7Yl|B5^o?0X$9i4pH35+gPPP9 z;dMQ&NUtJr$GTPcQEK%`!XjoW@V6Eq#kqDfSc4NsAT!b9c`!=+K>HHbK1+{dtb7j9 zYiHVG*zp$7is5Iw?(#YPmf1!EfI#>SteqC%z(TyALOU#41-usJFf}+IW(0&Jie~$pmzPYg*YAE`w^-V;WaC70=v3{-{AGg=7|UrG7W@} z#~92<_BPo2Zl0fE17X5W7_0pTe#F%3;u>l}7p`IjHYoKQPxwc^UQh;(fQ_eft<8_y zPXNdG6T706;29RDy=$p4L2?rU+pgS{o3w7S35+qTxGvs8Fq@~QSj-uD!NNnf#ic3Z z#8HnT3*JP*gz6a@(>lII+|=(qvw7a`47sU}|HAu^^gh4RW-aD}@R~;=wJgIW)GAPZVfv?eZhl~|R1)7RjD{C@iQrHW>iT7gqES*l!Y9<30Y?^P_ z_x={`SGuv9H}sWIjs4@fSiUlK7$zvvsbraZaq_>Ph-`xmLA&p#_Q^zlTHdp z!hsrI&Kj{@)QPSBdUiXI^~O#ihB{Wy59`}j8w|KBiu1qHK5g4ySid$SK2yll_<6U% z)%0y^1B9TB-2^5?0bo?9+;lFD<qgd+n>8cPQ}(+Fq&|Cl9kX z7p<&iV(3zq&*ULR7JrG4Rr~&X7M0h>67|<)G_sa=Nt*089u}xd$F(17m~4(2ovj_X zF!?^;lH~vlL3fTbSI$@;tzw!?)=!g9ls4ar)?eI=1jMy%S$+kk#Hqcb(JN@W4}#bO z@+07f`S@4rTo)%;N-H{oj(D(_BEr=`mOrq+x zQ?0b$X%o2+=vBfNFA-+0(zot6L6y38{=U0`>T#ELts?cw^y93?mrf4=-5~M}vGpXB zVv^UVK6A~I+W2a@zubsn~ zPz>U{q0|Woj*dUq<*N0GBNAS;4?con;YHFfRS;C0wiX}Ed~KP|`}0Wj8v?EB^k|WX zC_Z;5Oye-X{FC?nFUaDsh zJ2>38Y?LoL772xUfdmB&kf0FL4y{DUX-Z-LiCjg>JIxkfn&Aq?a_{?%?e86#1yp_& z?$*xn?Z$jcN9zTQC?-hHkM-U1t|niJuSjxKO_^1cF$2eF!~gpj?E?`kjU@O7IEWJ_ z5@%%+-P`b5sNLNE-z*0AS0e*c(;Ul;h3p0VWs0PaSKHCMEFA%TRXf!q!rj0(bg#X% zAY5z1jKmzqZ}~S=c2s?c_ErTPgnE)v{k!aPj%RPwa0*B((Xv*z8RcdmG#Cf`+rsCn zc~p(r_4?E6%z1Jm3%~5ae1B9tT_1QYg!C%hu2QjncPVI)-8 z=nEp^Z~qS~f*!q5UUX|T#x@>|R&*1z=0TJ0u<}irhk>P@Crx4}&sjEGFNBjcY#>5# zt$6qaGcfT*xA@H0nT#3o-kyc)emh5sCJ-F@y!Uy?UpiE+^%eD+pg)?_`6n%X+(`e$ zI~lg6NA4e0jS-L;J+gqDF<=1`>rO#%Vto=nu^JK2&sfqrmGb7nzjHIwd10V$!L>JP z?D!n-wEGyX?|{T7gH+9Jk5P~|foD=AFUtS$=bv8YMDQR#la7-n>Yt@VY_kMJ|K)Mi z6D&f@0r|lkWBP({&PSEf_V~>kQ<2l#|>9_X{7~+h+f!VoPf6kvN?QUA<1Sw6&D0%=*cSj6Q39ef@T! zUY`zd?*9%;b$5YtWcdI6qe-tWM*3<5liFzuDW&Sevg$m@Jw8<0R|e;4%k8=Z7zUyZ z2LWp}Y2E7_M3*M_tJt1<>QJlpt+E0k8dw4@eGxxbQSeyOvtT-R5h;L%@(jId(h)4m z6RkGqCWn{z{p0la-g~`H+Y&aN&W0pp??fQltI^+?MlPOJCmtkDc0_zv?DMq{ZRm6GBc%Tr`E#p=3uYfV0J1jUV~w9}oNEXe z{I5*u69r%E!PEHYz%}9zW1F89UB7|tyQc>YFbDU>5!{d%LatOBF&%s_5#_E=q zr32$;w2ezc^K4@O@Ko2;2D=-HU>#||aqs^xAF!{&6Hklk0UroP1`rAOV z{%;BiQ{4$=x<8k}|8H=2R(1Viof|oGaJ%wH*LD7?6NS%ePkHhYNYzbD;99I9)bJVh za?V62Z9#?va8rg9L=Z31G!8l5O-f`o=(W4wwO>t#J5j|Cdn`{~7$}I5(rPY&Pqxpt zduY>H_j{ac$S5#R^$)}cBzYg_nbaVigx*-4pQfp6`mw(w0Z(~t3jA881&}BF7qa~u zx`ETrd=sMlf7npu_e|}7Gb*tkl2A$CwAS=jQP>(NQoRD&z*)?}BDLY|)}a$k!>QC$ zzVY81pZHCSHL>5#tmnTFn5D5xCUIJs=1Tur+L;D_q``ec|LozRqa}61MIc_jLN&C@ z-}I1tlfW#z&ClpH&;ARr8E=^)_%hmeovD#!M|NG%>B`NW{np9%1R}r8pBMYE0cEP7 zV}Z~xdDDzLFQEB{$B^Dtai5BXsxH~E?;bUV?m%mp|4*%<`?sN7pfeYc|J_b{uTMSy zIutMRV&JFk#rxJ_Egw}y#cN9rzjnpkij|`Yh?qR<|5Y(T)FQN=vL(5`*kn8Hs_o9T zE?lgtDsMYl$`~+Zq^}TvwV|-8|61ho4J{b9k;+n3{FP$B9Uzaw&|tv+Z@pWczrL7) z^J6ZdZXoV$#FXE;(kS(xdLr9{PIO0M^+4%7v2p!KL^*Bw5d)5Dyb)I_)o6Ht9^3!P zG2=T!J!3~M*^Y0TvTXileXKmDo8ue4GhJCU&mD#a4eb+CdjX8RyD@PF{IFzBR1#|Z z?&@E8M_#n*pUUV%!w+q3b|=oy#j+SEQ&DfVtwpog$lSl>&7F7oM&G)*3zeS7>nE-n zGQJr~esU+C{ba!18kh04Eq~plJQ7a())6QaY_vUp%JMEU+vv?`jKK;5_C*j|{i%l+ zb1c|q{iig20#v9|`}a0vib)q32-9S?nRf=72FoQ>k8K67_PSx(TVFM;wjGshen#F= zrS?Br$G3BC%fG*u2w4wWW-d1Hv4$))7as*s?@&EI!wqEBoq|s~AO-1F9A@-A=RWag zb~3?y-m_cV{D05B!EjP;9#B_El%5FVI#k)rGbG@()DO?6%m|ZLu*yN_zxop)Z8Er| zj#n)9J9wX)K&vb`H(ma;y^=XR-45+Ezm>cyJ)$DlzF{XU!dG^uU<;p?oldy8S&=j- zmEsKz;@mD%P_pAe2Q7y+RX!xV>Rb=xqt<@-ly1g_*d~9w=^B%S#Mb_&?Tw@ILzhhb z#CRW$RS#z%F!*ww+*nOLEJ2CeDMWq0EoXwz|BQ+@gTk~jEfyv^bI}cCb%su-`@Mcn zPpieXtDP6n-MOiR_ng}(!PSG^;|w31Vn)laxHsRgW}~SZf__fRK>gP?>B~6zPwIhx zIzp}fE(dml_gX~1L5X*|Zjs@TB`XKYoR4EvAwy$Oz3|zsMTXgDZ;pYwiB2-)hZ#Iw z1Wg07r~XZdFH+IqgR@K+0-bGy0wRBZS7dA-^)1|PgOR{j3NphkmeWY)y&BBupL!Fs z>Ay`|!I>Z-pcio4hrdC|cC=AKd_43Up0F?hTcQgL-!WEEZnZ#|6f%|i!sacHQi&ea;%&={} zt2D}An8V;IjJ|ZC42X(`10M3)7!Va^`b~O#)*fRnr8jDj=7Es6R2j7BPGqI9@k{Y4 z7N5$i#(B1s&vbp(cE6NN1HYNS0R(Zk-eO^>GuOX?325d^Z&bK`eHNVWmqRH&Mu9K* zjBV;d-2K#28W)<9X7$TyV|z)(O(x1O36l|SNAnBpdFKja$4)-r2z&;P=*e>&SsVf( z!T(oCjQ&UBQHS(=G{Jn#PPkwbU!8i)>8K^dapnJIr7XjTYUM|r)%Xkjy%4#oh$-rD zYi0*}S6)|+^>cD!+l);&;B+7PT?@e)&6HN0)`d2`Y3nBsd8xgCcv7)1YOgd$3;Ed& zx@s_xiI9VI<%D~J-7_llsCasR9?$bT)UGF2*|h(k@|6Dn-~Qivz+&gfPp^0=SrwWM R{x6(L>yDmU$t~-b{|n1GvjYGC literal 0 HcmV?d00001 diff --git a/docs/misc/stern-brocot.md b/docs/misc/stern-brocot.md new file mode 100644 index 00000000..3e0bd2fa --- /dev/null +++ b/docs/misc/stern-brocot.md @@ -0,0 +1,127 @@ +Stern-Brocot 树是一种维护分数的优雅的数据结构。它分别由 Moritz Stern 在 1858 年和 Achille Brocot 在 1861 年发现这个结构。 + +# 概述 + +Stern-Borcot 树从两个简单的分数开始: + +$$ +\frac{0}{1}, \frac{1}{0} +$$ + +这个 $\frac{1}{0}$ 可能看得你有点懵逼。不过我们不讨论这方面的严谨性,你只需要把它当作 $\infty$ 就行了。 + +每次我们在相邻的两个分数 $\frac{a}{b},\frac{c}{d}$ 中间插入一个分数 $\frac{a+c}{b+d}$,这样就完成了一次迭代,得到下一个序列。于是它就会变成这样 + +$$ +\begin{array}{c} +\dfrac{0}{1}, \dfrac{1}{1}, \dfrac{1}{0} \\\\ +\dfrac{0}{1}, \dfrac{1}{2}, \dfrac{1}{1}, \dfrac{2}{1}, \dfrac{1}{0} \\\\ +\dfrac{0}{1}, \dfrac{1}{3}, \dfrac{1}{2}, \dfrac{2}{3}, \dfrac{1}{1}, \dfrac{3}{2}, \dfrac{2}{1}, \dfrac{3}{1}, \dfrac{1}{0} +\end{array} +$$ + +既然我们叫这个数据结构 Stern-Brocot 树,那么它总得有一个树的样子对吧。来一张图: + +![pic](./images/stern-brocot1.png) + +你可以把第 $i$ 层的序列当作是深度为 $i-1$ 的 Stern-Brocot 树的中序遍历。 + +# 性质 + +接下来讨论一下 Stern-Brocot 树的性质。 + +## 单调性 + +在每一层的序列中,真分数是单调递增的。 + +略证:只需要在 $\frac{a}{b}\le \frac{c}{d}$ 的情况下证明 + +$$ +\frac{a}{b}\le \frac{a+c}{b+d}\le \frac{c}{d} +$$ + +就行了。这个很容易,直接做一下代数变换即可 + +$$ +\begin{array}{l} +&\frac{a}{b}\le \frac{c}{d}\\ +\Rightarrow &ad\le bc\\ +\Rightarrow &ad+ab\le bc+ab\\ +\Rightarrow &\frac{a}{b}\le\frac{a+c}{b+d} +\end{array} +$$ + +另一边同理可证。 + +## 最简性 + +序列中的分数(除了 $\frac{0}{1},\frac{1}{0}$)都是最简分数。 + +略证:为证明最简性,我们首先证明对于序列中连续的两个分数 $\frac{a}{b},\frac{c}{d}$: + +$$ +bc-ad=1 +$$ + +显然,我们只需要在 $bc-ad=1$ 的条件下证明 $\frac{a}{b}, \frac{a+c}{b+d}, \frac{c}{d}$ 的情况成立即可。 + +$$ +a(b+d)-b(a+c)=ad-bc=1 +$$ + +后半部分同理。证明了这个,利用扩展欧几里德定理,如果上述方程有解,显然 $\gcd(a,b)=\gcd(c,d)=1$。这样就证完了。 + +有了上面的证明,我们可以证明 $\frac{a}{b}<\frac{c}{d}$。 + +有了这两个性质,你就可以把它当成一棵平衡树来做了。建立和查询就向平衡树一样做就行了。 + +# 实现 + +构建实现 + +```cpp +void build(int a = 0, int b = 1, int c = 1, int d = 0, int level = 1) { + int x = a + c, y = b + d; + //... output the current fraction x/y + //at the current level in the tree + build(a, b, x, y, level + 1); + build(x, y, c, d, level + 1); +} +``` + +查询实现 + +```cpp +string find(int x, int y, int a = 0, int b = 1, int c = 1, int d = 0) { + int m = a + c, n = b + d; + if (x == m && y == n) return ""; + if (x*n < y*m) return 'L' + find(x, y, a, b, m, n); + else return 'R' + find(x, y, m, n, c, d); +} +``` + +# Farey 序列 + +Stern-Brocot 树与 Farey 序列有着极其相似的特征。第 $i$ 个 Farey 序列记作 $F_i$,表示把分母小于等于 $i$ 的所有最简真分数按大小顺序排列形成的序列。 + +$$ +\begin{array}{l} +F_1=\{&\frac{0}{1},&&&&&&&&&&\frac{1}{1}&\}\\ +F_2=\{&\frac{0}{1},&&&&&\frac{1}{2},&&&&&\frac{1}{1}&\}\\ +F_3=\{&\frac{0}{1},&&&\frac{1}{3},&&\frac{1}{2},&&\frac{2}{3},&&&\frac{1}{1}&\}\\ +F_4=\{&\frac{0}{1},&&\frac{1}{4},&\frac{1}{3},&&\frac{1}{2},&&\frac{2}{3},&\frac{3}{4},&&\frac{1}{1}&\}\\ +F_5=\{&\frac{0}{1},&\frac{1}{5},&\frac{1}{4},&\frac{1}{3},&\frac{2}{5},&\frac{1}{2},&\frac{3}{5},&\frac{2}{3},&\frac{3}{4},&\frac{4}{5},&\frac{1}{1}&\}\\ +\end{array} +$$ + +显然,上述构建 Stern-Brocot 树的算法同样适用于构建 Farey 序列。因为 Stern-Brocot 树中的数是最简分数,因此在边界条件(分母)稍微修改一下就可以形成构造 Farey 序列的代码。你可以认为 Farey 序列 $F_i$ 是 Stern-Brocot 第 $i-1$ 次迭代后得到的序列的子序列。 + +Farey 序列同样满足最简性和单调性,并且满足一个与 Stern-Brocot 树相似的性质:对于序列中连续的三个数 $\frac ab,\frac xy,\frac cd$,有 $x=a+c,y=b+d$。这个可以轻松证明,不再赘述。 + +由 Farey 序列的定义,我们可以得到 $F_i$ 的长度 $L_i$ 公式为: + +$$ +L_i=L_{i-1}+\varphi(i)\\ +L_i=1+\sum_{k=1}^i\varphi(k) +$$ + -- 2.11.0