number theory數(shù)論研究整數(shù)性質(zhì),是數(shù)學(xué)一門(mén)重要分支

偏向于應(yīng)用,但理論不失嚴(yán)謹(jǐn)胡淵 數(shù)論與信息學(xué)競(jìng)整胡淵 數(shù)論與信息學(xué)競(jìng)m為商0r<b為余數(shù)(ramod胡淵胡淵 數(shù)論與信息學(xué)競(jìng)整除的??胡淵 數(shù)論與信息學(xué)競(jìng)胡淵胡淵 數(shù)論與信息學(xué)競(jìng),,,一大類(lèi),, ?胡淵 數(shù)論與信息學(xué)競(jìng)胡淵胡淵 數(shù)論與信息學(xué)競(jìng)?cè)绻粋€(gè)大于1的數(shù)的約數(shù)只有1和其本身,則稱(chēng)其為質(zhì)數(shù). (a,b)如果兩個(gè)數(shù)沒(méi)有大于一的公約數(shù),即 (a,b)=1,則稱(chēng)a,b互質(zhì),記作a⊥b歐幾里得.+,b即最大公約數(shù)相同取n=?bac則有a+nb=amodb.b (b,amod,為O(logmax(a,b)).(代碼?)胡淵 數(shù)論與信息學(xué)競(jìng)胡淵胡淵 數(shù)論與信息學(xué)競(jìng)x2≡1(modP)→x≡±1(modP質(zhì)因子,,胡淵 數(shù)論與信息學(xué)競(jìng)胡淵 數(shù)論與信息學(xué)競(jìng)簡(jiǎn)胡淵 數(shù)論與信息學(xué)競(jìng),,,,為a的逆元,記作a?1冪,a?1≡aP?2(modP)),炫耀數(shù)論知識(shí)等胡淵 數(shù)論與信息學(xué)競(jìng)費(fèi)馬小定理胡淵 數(shù)論與信息學(xué)競(jìng)有{a2a(P1)a}兩兩不同余于是其在modP意義下即(P1)!aP?1(P1)!(modP)兩邊消去(P1)!,定理得證胡淵 數(shù)論與信息學(xué)競(jìng)胡淵 數(shù)論與信息學(xué)競(jìng)利用費(fèi)馬小定理配合快速冪,很容易求出一個(gè)整數(shù)的逆元時(shí)間雜度為O(nlogP)bP/ici=P?PmodbP/ici≡?Pmodi(modP?bP/ic(Pmodi)?1≡i?1(modP從小到大計(jì)算i1時(shí)由于Pmodii,其逆元已經(jīng)算出胡淵 數(shù)論與信息學(xué)競(jìng)Wilson胡淵 數(shù)論與信息學(xué)競(jìng)?cè)绻鸓是質(zhì)數(shù)有(P11(modP證明思路:P5時(shí),(P1)!中去掉1和P1,別的項(xiàng)總可以和,胡淵 數(shù)論與信息學(xué)競(jìng)質(zhì)數(shù)胡淵 數(shù)論與信息學(xué)競(jìng)顯然每個(gè)合數(shù)n都存在一個(gè)≤√n的因子直接枚舉這個(gè)因子可.是否是質(zhì)數(shù).對(duì)于一個(gè)給定的數(shù)P(不一定是質(zhì)數(shù)),隨機(jī)一個(gè)在[2P?1)的數(shù)利用快速冪判斷是否有aP?1modP=反例:2340≡1(mod341)反例確實(shí)不多,但是不能忽略胡淵 數(shù)論與信息學(xué)競(jìng)Miller-Rabin素?cái)?shù)判胡淵 數(shù)論與信息學(xué)競(jìng),對(duì)于可能的P選定一些a[2P1),假設(shè)P1=2Kr,其中如果P為質(zhì)數(shù)則a2KrmodP=1,根據(jù)判斷題有a2K1rmodP=±1.類(lèi)似的,對(duì)于k[0K),都可以做這個(gè)判斷如果a2k1rmodP=1a2krmodP6=±1則可推出P質(zhì)數(shù).具體計(jì)算時(shí)只要先算出armodP然后不斷平方時(shí)間復(fù)雜度仍然為O(logP)生成范圍內(nèi)所有 胡淵 數(shù)論與信息學(xué)競(jìng),),,法O(nlog胡淵 數(shù)論與信息學(xué)競(jìng)補(bǔ)充知識(shí):積性胡淵 數(shù)論與信息學(xué)競(jìng)胡淵 數(shù)論與信息學(xué)競(jìng)補(bǔ)充知識(shí):積性胡淵 數(shù)論與信息學(xué)競(jìng),,胡淵胡淵 數(shù)論與信息學(xué)競(jìng)關(guān)鍵問(wèn)題是求出φ(pq)的值成pqpq?1(為什么經(jīng)典P P i j i j=1

(i,j給定整數(shù)n，求1≤x,y≤n且 1n+2n+...+P

Pb=1Blcm(a,b) 胡淵 數(shù)論與信息學(xué)競(jìng)墨墨的 究a1x1+a2x2++anxn=B存在非負(fù)整數(shù)解的條件，他要求你編寫(xiě)一個(gè)程序，給定N,an,B的取值范圍，求出有多少B N≤12,0≤ai≤4×10,1≤Bmin≤Bmax≤胡淵 數(shù)論與信息學(xué)競(jìng)胡淵胡淵 數(shù)論與信息學(xué)競(jìng) 則2x和3x不能在該子集中。 胡淵 數(shù)論與信息學(xué)競(jìng) ，火星人要jyy用飛船上的瓶子來(lái)?yè)Q.jyy的飛船上共有N個(gè)瓶子1≤N≤1000，經(jīng)過(guò)協(xié)商，火星人只要其中料給jyy.為Vi(Vi為整數(shù),并且滿足1≤Vi≤ ).火星人并不會(huì)把 來(lái)交差.jyy當(dāng)然知道他們會(huì)來(lái)這一手,于 胡淵 數(shù)論與信息學(xué)競(jìng)a0+a1x+a2x2+...+anxn=

≡

(modPnmmodPnO(nm)?O(n)?O(P2)?O(logPn,m,P≤例題:離散對(duì)給定質(zhì)數(shù)Pab求滿足axb(modP)的最小的x.根據(jù)費(fèi)馬小定理有x[0P2).計(jì)算O(P)不好意思,P=1014胡淵 數(shù)論與信息學(xué)競(jìng)給定nn一次詢問(wèn):O(√n

i

nbi?≤補(bǔ)充知識(shí):求離散對(duì)數(shù)的大步小步算取一個(gè)接近P√數(shù)M,x顯然具有sM+r的形式 得asM+r≡b(modP有arba?sM(modP)對(duì)于r[0M)將結(jié)果存在Hash表中這樣做復(fù)雜度O(PlogP胡淵 數(shù)論與信息學(xué)競(jìng)胡淵 數(shù)論與信息學(xué)競(jìng)擴(kuò)展知識(shí)