信息學(xué)之?dāng)?shù)學(xué)基礎(chǔ)

1、第一章有關(guān)數(shù)論的算法1.1最大公約數(shù)與最小公倍數(shù)1.2有關(guān)素數(shù)的算法1.3方程axby=c的整數(shù)解及應(yīng)用1.4求a^bmodn1.11.1最大公約數(shù)與最小公倍數(shù)最大公約數(shù)與最小公倍數(shù)1.算法1:歐幾里德算法求a，b的最大公約數(shù)functiongcd(ab:longint):longintbeginifb=0thengcdd:=aelsegcd:=gcd(bamodb)end2.算法2:最小公倍數(shù)acm=abdivgcd(ab)3.算法3

2、:擴展的歐幾里德算法，求出gcd(ab)和滿足gcd(ab)=axby的整數(shù)x和yfunctionexgcd(ab:longintvarxy:longint):longintvart:longintbeginifb=0thenbeginresult:=ax:=1y:=0endelsebeginresult:=exgcd(bamodbxy)t:=xx:=yy:=t(adivb)yendend（理論依據(jù)：gcd(ab)=axby=bx1(a

3、modb)y1=bx1(a(adivb)b)y1=ay1b(x1(adivb)y1))1.1.2有關(guān)素數(shù)的算法有關(guān)素數(shù)的算法1.算法4:求前n個素數(shù):programBasicMath_Primeconstmaxn=1000varpnumn:longintp:array[1..maxn]oflongintbeginreadln(n)mainoutend.2.算法5:求不大于n的所有素數(shù)programsushu3constmaxn=1000

4、0varikn:integera:array[1..maxn]ofintegerbeginreadln(n)fi:=1tondoa[i]:=ia[1]:=0i:=2whilei0thenbeginwrite(a[i]:5)k:=k1ifkmod10=0thenwritelnendend.3.算法6:將整數(shù)分解質(zhì)因數(shù)的積programBasicMath_PolynomialFactsconstmaxp=1000varpnumn:longi