劉汝佳-1數(shù)論初步.ppt

《劉汝佳-1數(shù)論初步.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、2005年浙江省隊培訓(xùn)第1講數(shù)論初步劉汝佳目錄一、基本概念二、進(jìn)位制三、模算術(shù)與方程四、雜題一、基本概念基本概念整除與約數(shù)、倍數(shù).注意負(fù)數(shù)可整除性的基本性質(zhì)若a

2、b,a

3、c,則a

4、(b+c)若a

5、b,那么對所有整數(shù)c,a

6、bc若a

7、b,b

8、c,則a

9、c整除關(guān)系具有傳遞性.它是偏序關(guān)系(partialorder),<

10、,Z>是一個格素數(shù)和合數(shù)如果大于1的正整數(shù)p僅有的正因子是1和p,則稱p為素數(shù)(prime)大于1又不是素數(shù)的正整數(shù)稱為合數(shù)(compound)如果n是合數(shù),則n必有一個小于或等于n1/2的素因子算術(shù)基本定理每個正整數(shù)都可以惟一地表示成素數(shù)的乘積，其中素

11、數(shù)因子從小到大依次出現(xiàn)（這里的“乘積”可以有0個、1個或多個素因子）。換句話說,任意正整數(shù)n可以寫成n=2a1*3a2*5a3*…,其中a1,a2,a3等為非負(fù)整數(shù)這個定理也叫做惟一分解定理。它是一個定理而不是公理！雖然在大多人看來，它是“顯然成立”的，但它的確是需要證明的定理除法和同余令a為整數(shù)，d為正整數(shù)，那么有惟一的整數(shù)q和r，其中0≤r

12、2=24….7余數(shù)可以作為原數(shù)的一個signature(標(biāo)記).如果標(biāo)記下的運算錯誤,一定錯誤如果標(biāo)記下的運算正確?最大公約數(shù)和最小公倍數(shù)令a和b是不全為0的兩個整數(shù)，能使d

13、a和d

14、b的最大整數(shù)稱為a和b的最大公約數(shù)，用gcd(a,b)表示，或者記為(a,b)。令a和b是不全為0的兩個整數(shù)，能使a

15、d和b

16、d的最小整數(shù)稱為a和b的最小公倍數(shù)，用lcm(a,b)表示，或者記為[a,b]定理:ab=gcd(a,b)*lcm(a,b)定理的證明使用惟一分解定理.設(shè)則有:容易驗證定理成立例題：佳佳的困惑給出一個數(shù)N，含數(shù)字1、2、3、4，把N的所有數(shù)字重新排列一下組成一個新

17、數(shù)，使它是7的倍數(shù)。分析把數(shù)字1、2、3、4從中抽出，然后把其他數(shù)字按照原順序排列（事實上，怎么排列都無所謂）組成自然數(shù)ww*10,000整除7取余有7種可能，即是為0、1、2、3、4、5、6。這時如果能用數(shù)字1、2、3、4排列出7個數(shù)，使它們整除7取余的值分別為0、1、2、3、4、5、6，把這個4位數(shù)接在w后面即為問題的解。例題：街道數(shù)找所有的(n,k),滿足:1+2+..+(n-1)=(n+1)+(n+2)…+k輸出按k排序的前10個分析整理得:n(n-1)=(k-n)(n+k+1)化簡得:k2+k-2n2=0,即n2=k(k+1)/2由于k和k+1互素,因此要么

18、k是完全平方數(shù)要么k/2是完全平方數(shù)分別設(shè)k=m2和2m2,枚舉m例題：齒輪假設(shè)有三種齒輪：6齒，12齒，30齒。想要實現(xiàn)4:5的比例，一種可行方案如下：給定可用的齒輪（每種均有無窮多），設(shè)計一系列傳輸c1:d1,c2:d2,…,cm:dm，使得其綜合比例(c1c2c3…cm)/(d1d2d3…dm)為給定值a:b。給定齒輪的齒數(shù)為5到100，a和b不超過10000。分析使用惟一分解定理,單獨考慮各個素因子c1=p1a1*p2*a2*…c2=p1b1*p2*b2*……則c1x*c2y=p1(x*a1+y*b1)*p2(x*a2+y*b2)目標(biāo)a:b=p1z1*p2z2

19、…x*a1+y*b1=z1;x*a2+y*b2=z2分析第i個齒輪的使用情況用xi表示，xi>0表示用在分子xi次，xi<0表示用在分母-xi次。由于ai<=100，只需要考慮100以內(nèi)的25個素數(shù)考慮每個素數(shù)pi的指數(shù)，可以構(gòu)造一個線性方程，共25個等式分子分母個數(shù)相等，故所有xi的和為0，消元后枚舉獨立變量例題：破解RSA給定M個數(shù)，它們的質(zhì)因子在前T個質(zhì)數(shù)范圍內(nèi)。求這M個數(shù)組成集合的滿足如下條件的非空子集個數(shù)：子集中所有數(shù)的積為完全平方數(shù)。分析首先將讀入的M個數(shù)，分解質(zhì)因數(shù)，并對每個質(zhì)因數(shù)出現(xiàn)次數(shù)的奇偶性進(jìn)行記錄。設(shè)x[i]=0或1代表是否使用第i個數(shù)?？梢粤谐?/p>

20、一個關(guān)于x[i](1<=i<=m)的位方程組（乘積的所有質(zhì)因數(shù)出現(xiàn)次數(shù)均為偶數(shù)）。解該方程組，檢查最后有多少自變量，設(shè)有n個，那么結(jié)果應(yīng)該是2n-1（除去空集）。時空復(fù)雜度均為O(M2)思考：傳球游戲N個人圍圈玩?zhèn)髑蛴螒?，開始時第一個人拿著球，每個人把球傳給左手的第K個人。滿足1≤K≤N/2。求K的最大值，使得第一個人重新拿到球之前，每個人都拿過球?；締栴}如何求1~n的所有素數(shù)?如何判斷一個數(shù)n是否為素數(shù)?如何求兩個數(shù)的最大公約數(shù)?如何給一個數(shù)n分解素因數(shù)?問題1:1~n的素數(shù)假設(shè)要求1~100的素數(shù)2是素數(shù),刪除2*2,2*3,2*4,…,2*5