有關數(shù)論的算一、求最大公約，首先來回顧一下公約數(shù)和最大公約數(shù)的概念：如果d是a的約數(shù)并且也是b的約d是a與b的公約數(shù)。例如，30242430的公約數(shù)是１，2，3，6。1兩個不同時為0的整數(shù)a與b的最大公約是其值為最大的公約數(shù)，表示為(a，b)。的，因為(a，b)＝(│a│，│b│)。a和bab的最大公約數(shù)， ，(a，b)＝(b，amod(證明b)。將amodb化成a與b的線性組amodb＝a－ada和bda與bd能整除(amodb)。又因為ｄ能整除b和(amodb)，顯然d(＝(a，b))能整數(shù)(b，amodb)。同理可證：(b，amodb)能整除(a，b)由此得出直接基于定理之上的遞歸function(a，b：longint)：longint；ifthen ←(b，amodb)下面，對算法進行推廣，使得該算法不僅能得出任意兩個正整數(shù)a和的最大公約數(shù)d，而且還能計算出滿足下式的整系數(shù)X和Y (X與Y可能為0或負數(shù))函數(shù)extenden_輸入整數(shù)a，b，返回(a，b)和對應等式ax+by中的x，y。functionextended_(a，b：longint；varx，y：longint)：longint；ifthenelseextended_←extended_(b，amodb，x，y)；t←x；x←y；y←t-(adivb)*y上述函數(shù)是從算法衍生出來的.算法一開始，它首先測試若b=0，返回當前最大公約數(shù)為a，x=1y=0，以使a=的x＇和y＇。在這種情況下，有d= (a，b)=d＇=(b，amodb)。為了得到滿足d=ax+by的x和 利用等式d=d＇-bx＇+(amodb)y＇得d=bx＇+(a-a*b)y＇=ay＇+b(x＇-a 因此， 選擇x=y＇，y=x′-a*y＇就可以滿足等式d=ax+by。顯然這個算法是正Abaxy13-333-13-36231-63230130310a≡b(mod表示(amodn)=(bmodn)a和bn是相等的(a和bn有相同的余ax≡b(mod a、b和nn的x值.x解。 表明X＇是方程ax＇≡d(modn)的一個解。然后分析若dbax≡b(modn)d個解.1x0=x＇*bmoddd-1n加上(n/d)xi=(x0+i*n)mod d荒島野23612，…，MNC1，C2，…，CNi野人會沿順時針向前走Pi個洞住下來。每個野人i有一個值Li，即生存的年數(shù)。下面四幅圖描述了一個有6個山洞，住有三個野人的島上前四年的情況。三個野人初始的編號依次為1，2，3；每年要走過的數(shù)依次為3，7，2；值依次為4，3，1。2361453546453546112126 3635454圖 圖 輸入文件savage.in1行為一個N(1≤N≤15)即野人的數(shù)目2到第N+1每行為三個整數(shù)CPL(1≤C，P≤100，0≤L106)，表示每個野人所住的初始洞 10631342733216算法分ci為第iijpab[i，jpipj，第

cicjfori←1ton forj←i+1tondopab[i，j]←p[i]-p[j]；cab[i，jc[j]-c[iijifpab[i，j]<0thenpab[i，j]←-pab[i，j]；cab[i，j]←-cab[i，j]pab[i，j]x，m的數(shù)。顯然，若p[i，j]*x和c[i，j]除以m有相同的余數(shù)，則說明在x年第i個野人和第j個野人處于同一個。的目的就是要尋找最小的m，使得任何一對野人在有生之年不會相遇，即p[i，j]*x≡c[i，j](modm)在（1‥min{l[i]，l[j]}）范圍內無解（1≤i≤ni+≤j≤為了計算a*x≡b(modm)的最小正整數(shù)x，首先通過輾轉相除法計算a和m的(a，m，d，x，y)procedure(a，b：longint；vard，x，y：longint)；{通過輾轉相除法計abdax+by=dx、y}varc，t：longint；c←amodb；ifc=0thenbegind←b；x←0；y←1；end{then}elsebegint←x；x←y；y←t-adivb*y；end；{d≠0整除（bmodd=0a*x’m*y’=1x’，(x’*b+m)modm

bmodm)xijxmin{lil[j]}若所有可能的野人對都滿足上述條件則確定數(shù)可維持島上的和平。functioncheck：boolean；{若m是所有野人在有生之年保持安全的最小數(shù)，則返vari，j，mm，a，b，d，x，y，ans：longint；fori←1tondo forj←i+1tondo x、ifbmodd<>0thencontinue； {若ij不會相遇，則枚舉a←adiv {計算d=(a,m)和滿足a*xm*yx、b←bdivd；mm←mdiv

ans=(x*b

mwhileans<0doans←ans+mm；whileans>=mmdoans←ans-mm；if(ans≤l[i])and(ans≤l[j]) {如果野人ijfalse}thenexit； end；{check}顯然，所有野人在有生之年保持安全的數(shù)m至少是max=max