2005年浙江省隊(duì)培訓(xùn)

第1講數(shù)論初步劉汝佳目錄一、基本概念二、進(jìn)位制三、模算術(shù)與方程四、雜題一、基本概念基本概念整除與約數(shù)、倍數(shù).注意負(fù)數(shù)可整除性的基本性質(zhì)若a|b,a|c,則a|(b+c)若a|b,那么對(duì)所有整數(shù)c,a|bc若a|b,b|c,則a|c整除關(guān)系具有傳遞性.它是偏序關(guān)系(partialorder),<|,Z>是一個(gè)格素?cái)?shù)和合數(shù)如果大于1的正整數(shù)p僅有的正因子是1和p,則稱p為素?cái)?shù)(prime)大于1又不是素?cái)?shù)的正整數(shù)稱為合數(shù)(compound)如果n是合數(shù),則n必有一個(gè)小于或等于n1/2的素因子算術(shù)基本定理每個(gè)正整數(shù)都可以惟一地表示成素?cái)?shù)的乘積，其中素?cái)?shù)因子從小到大依次出現(xiàn)（這里的“乘積”可以有0個(gè)、1個(gè)或多個(gè)素因子）。換句話說(shuō),任意正整數(shù)n可以寫(xiě)成n=2a1*3a2*5a3*…,其中a1,a2,a3等為非負(fù)整數(shù)這個(gè)定理也叫做惟一分解定理。它是一個(gè)定理而不是公理！雖然在大多人看來(lái)，它是“顯然成立”的，但它的確是需要證明的定理除法和同余令a為整數(shù)，d為正整數(shù)，那么有惟一的整數(shù)q和r，其中0≤r<d，使得a=dq+r可以用這個(gè)定理來(lái)定義除法：d叫除數(shù)，a叫被除數(shù)，q叫商，r叫余數(shù)。如果兩個(gè)數(shù)a,b除以一個(gè)數(shù)c的余數(shù)相等，說(shuō)a和b關(guān)于模c同余，記作a≡b(modc)同余為什么有同余?13241234…1+432435..2=24….7余數(shù)可以作為原數(shù)的一個(gè)signature(標(biāo)記).如果標(biāo)記下的運(yùn)算錯(cuò)誤,一定錯(cuò)誤如果標(biāo)記下的運(yùn)算正確?最大公約數(shù)和最小公倍數(shù)令a和b是不全為0的兩個(gè)整數(shù)，能使d|a和d|b的最大整數(shù)稱為a和b的最大公約數(shù)，用gcd(a,b)表示，或者記為(a,b)。令a和b是不全為0的兩個(gè)整數(shù)，能使a|d和b|d的最小整數(shù)稱為a和b的最小公倍數(shù)，用lcm(a,b)表示，或者記為[a,b]定理:ab=gcd(a,b)*lcm(a,b)定理圍的證俘明使用籃惟一戲分解努定理梯.孝設(shè)則有許:容易何驗(yàn)證盡定理糊成立例題醋：佳森佳的達(dá)困惑給出菊一個(gè)兵數(shù)N，含冶數(shù)字喚1、撓2、栗3、歪4，范把N的所籌有數(shù)蠢字重嶼新排膨列一蔥下組蜻成一晨個(gè)新旅數(shù)，裂使它濕是7款的倍紙數(shù)。分析把數(shù)壘字1顯、2勒、3陸、4邁從中炒抽出狂，然材后把虎其他里數(shù)字答按照砍原順?biāo)蚺爬校ㄎ檬聦?shí)勇上，站怎么井排列木都無(wú)熔所謂徹）組拐成自面然數(shù)ww*10芳,0雜00怪整除怠7取桑余有潤(rùn)7種鈴可能刻，即首是為括0、母1、奸2、板3、抹4、挎5、六6。頑這時(shí)邊如果很能用頁(yè)數(shù)字籍1、秧2、受3、微4排粉列出蔽7個(gè)態(tài)數(shù)，僑使它權(quán)們整旗除7亦取余妙的值淋分別寶為0唇、1少、2產(chǎn)、3敏、4仿、5蘆、6李，把存這個(gè)甚4位背數(shù)接透在w仇后面陷即為時(shí)問(wèn)題坊的解趙。例題登：街巷道數(shù)找所護(hù)有的惜(n仰,孝k)仍,眉滿足咐:1+使2+泊..侵+(蜂n-累1)歌=(冷n+撫1)疊+(瞞n+逢2)洞…+堪k輸出智按k宣排序劇的前燒10避個(gè)分析整理杯得:勺n灣(n仿-1冠)=獻(xiàn)(k室-n耗)(屯n+認(rèn)k+柏1)化簡(jiǎn)賠得:靜k2+k鍵-2雨n2=0懸,悶即n2=k芬(k覽+1匹)/捉2由于吩k和輝k+籍1互捆素,竊因樓此要么澇k是漆完全武平方撫數(shù)要么堆k/罷2是邪完全悲平方僻數(shù)分別授設(shè)k敗=m2和2猾m2,桃枚舉鹿m例題向：齒費(fèi)輪假設(shè)目有三靜種齒亞輪：閉6齒積，1閉2齒酸，3嘩0齒父。想繡要實(shí)掛現(xiàn)4贊:稠5業(yè)的比芬例，晚一種哨可行縣方案瘡如下漸：給定鼻可用繩的齒限輪（仍每種賢均有敬無(wú)窮糞多）援，設(shè)蹄計(jì)一更系列從傳輸c1:d1,c2:d2,曾…,cm:dm，使襯得其蛇綜合輸比例很(c1c2c3…cm)/法(d1d2d3…dm)為炊給定崗值a:b。給定搖齒輪惜的齒寧數(shù)為堆5到熄10皮0，a和b不超泛過(guò)1有00老00待。分析使用旨惟一云分解小定理味,禮單獨(dú)披考慮能各個(gè)廈素因辱子c1必=婚p鄉(xiāng)豐1a1*p尺2*a2*…c2色=婦p之1b1*p塊2*b2*……則c1x*c2y=p島1(x預(yù)*a蜘1+緊y*差b1卸)*p引2(x*a2膽+y捷*b度2)目標(biāo)響a:承b削=改p1z1*臣p2z2…x*a魄1+y*b錘1=喬z1震;止x*彼a2輛+y展*b陸2=扶z2分析第i個(gè)齒癢輪的胞使用介情況悄用xi表示敬，xi>0杠表示洲用在尚分子xi次，xi<0蹲表示明用在場(chǎng)分母他-xi次。由于ai<=藏10皂0，讓只需叔要考云慮1兼00短以內(nèi)鬼的2菊5個(gè)駝素?cái)?shù)考慮荒每個(gè)屑素?cái)?shù)pi的指幕數(shù)，衣可以這構(gòu)造積一個(gè)汁線性搶方程屯，共慚25乞個(gè)等惡式分子放分母芹個(gè)數(shù)切相等丈，故維所有xi的和諷為0加，消元破后枚腐舉獨(dú)朽立變本量例題張：破商解R毫SA給定醬M個(gè)社數(shù)，欣它們敏的質(zhì)知因子兔在前府T個(gè)鐵質(zhì)數(shù)傻范圍撿內(nèi)。固求這獎(jiǎng)M個(gè)今數(shù)組免成集涂合的視滿足爐如下艘條件軌的非紗空子值集個(gè)熊數(shù)：域子集井中所恨有數(shù)窄的積簡(jiǎn)為完沙全平嚴(yán)方數(shù)種。分析首先鎖將讀悅?cè)氲睦颩個(gè)蹄數(shù)，閣分解覆質(zhì)因辨數(shù)，央并對(duì)魚(yú)每個(gè)御質(zhì)因儉數(shù)出盟現(xiàn)次號(hào)數(shù)的地奇偶授性進(jìn)扮行記關(guān)錄。設(shè)x疲[i書(shū)]=捎0或蛾1代等表是搖否使痛用第含i個(gè)鉗數(shù)。商可以澇列出愛(ài)一個(gè)泳關(guān)于旱x[貧i]胖(1您<=萍i<乞=m城)的接位方燥程組虧（乘五積的偷所有損質(zhì)因行數(shù)出禍現(xiàn)次浴數(shù)均違為偶帖數(shù)）瓦。解該腥方程艙組，帳檢查堪最后旱有多猴少自瞧變量駝，設(shè)籌有n驗(yàn)個(gè)，戀那么雨結(jié)果袍應(yīng)該息是2息n-李1（厭除去盜空集到）。琴時(shí)噸空復(fù)孤雜度斷均為循O(脾M2)思考顏：傳漸球游員戲N個(gè)矩人圍資圈玩早傳球手游戲美，開(kāi)烏始時(shí)援第一巴個(gè)人慢拿著熟球，啞每個(gè)陣人把目球傳旋給左形手的寇第K棕個(gè)人潔。滿愈足1存≤K咸≤N田/2腐。求席K的撓最大送值，隔使得洲第一索個(gè)人壯重新決拿到朗球之撲前，杜每個(gè)壺人都說(shuō)拿過(guò)央球?；拘迒?wèn)題如何摸求1踏~n扮的所室有素偽數(shù)?如何姥判斷焰一個(gè)醫(yī)數(shù)n竄是否醒為素捏數(shù)?如何散求兩流個(gè)數(shù)困的最誓大公歸約數(shù)堪?如何承給一塌個(gè)數(shù)臉n分請(qǐng)解素披因數(shù)餅?問(wèn)題夜1:貓1柏~n票的素語(yǔ)數(shù)假設(shè)崇要求來(lái)1~栗10折0的夸素?cái)?shù)2是棒素?cái)?shù)推,涌刪除狠2*翻2,廢2成*3鋼,含2*屈4,欣…削,理2*團(tuán)50第一腳個(gè)沒(méi)斃被刪焦除的嚷是3癢,兔刪除辭3*肚3,優(yōu)3膽*4歡,造3*吸5,忌…,塊3*缺33第一品個(gè)沒(méi)耽被刪旨除的維是5看,富刪除濃5*半5,甘5局*6暑,平…泊5*同20得到冤素?cái)?shù)誘p時(shí)燙,腹需要壤刪除逢p*弊p,晃p寧*(耽p+北1)鑄,貌…駁p*販[n勝/p濃],魂運(yùn)碧算量旁為[書(shū)n/族p]樓-p蔽,鐮其中們p不喬超過(guò)繡n1/曠2(想破一想聰,鼻為什點(diǎn)么)Er攻at階os買th孔en惠es館的篩游子小知蠟識(shí)剃()近似疏公式湊(L黑eg孝en瓜dr層e常次數(shù)B餅=-墓1.礎(chǔ)08抱36耍6)思考茂：正富多邊繞形給圓燈周上魚(yú)n個(gè)銀點(diǎn)的更坐標(biāo)諷,督能組狡成多捕少個(gè)級(jí)正多頁(yè)邊形肯？問(wèn)題戰(zhàn)2:憶素指數(shù)判蛙定枚舉欠法:剛O起(n1/想2),蛾指苗數(shù)級(jí)京別改進(jìn)察的枚捎舉法巧:井O(洗ph浸i(設(shè)n1/法2))芳=O持(n1/拖2/l倍og敢n)曲,枕仍然膀是指島數(shù)級(jí)段別概率扣算法包:額Mi繞ll缺er脂-R豈ab匯in戀測(cè)試袋+淘L抖uc茫as勢(shì)-L肆eh宵me醉r測(cè)譜試Mi蜂ll碧er飯-R衡ab辛in趴測(cè)試對(duì)于嚇奇數(shù)默n,靈記秩n=襲2r*s噸+1睜,耗其中塞s為峽奇數(shù)隨機(jī)麗選a密(1頃<=訊a<照=n濱-1宏),撿n夾通過(guò)峰測(cè)試瘡的條晌件是as≡1脂(m巷od酸n閉),組或艱者存在秋0<舊=j產(chǎn)<=疊r-練1使即得a2^慨j*慢s≡-珍1(勾mo極d慨n)素?cái)?shù)那對(duì)于即所有電a通岡過(guò)測(cè)商試,景合宮數(shù)通霸過(guò)測(cè)輩試的辨概率博不超呢過(guò)1慎/4只測(cè)催試a百=2帳,救3,釘5萌,割7,恥則證2.置5*遠(yuǎn)1013以內(nèi)孕唯一姨一個(gè)穴可以耗通過(guò)腹所有后測(cè)試步的數(shù)磁為3反21挺50侍31樂(lè)75翼1思考鴨：區(qū)畜間內(nèi)亡的素艘數(shù)給出翁n,房誠(chéng)m航(n步<=示106,飛m<持=1亂05),狹求遣n~恒n+敞m之昨間的矩素?cái)?shù)瞎有多頸少個(gè)哪種閥方法滾快?壁篩壺還是框依次高素?cái)?shù)華判定驚?問(wèn)題誼3:院最堂大公努約數(shù)方法始一:站使責(zé)用惟啟一分覺(jué)解定穩(wěn)理,陜先躍分解調(diào)素因鋪數(shù),胃然柏后求遙最大綠公約坦數(shù)方法途二:療(監(jiān)Eu甩cl唉id合算法惹)利化用公宅式g肝cd勺(a要,族b)前=g識(shí)cd奧(b巖,瞇a樸mo吐d挽b)乖,炭時(shí)間好復(fù)雜固度為仰O(坡lo釣gb池)方法影三:可(臺(tái)二進(jìn)薪制算周法)版若必a=插b,涉g耀cd程(a聾,b膽)=秀a,雀否栽則A和拳b均溪為偶位數(shù),懶g(shù)副cd克(a興,b畢)=裙2*姥gc宋d(屠a/世2,退b/夠2)A為乞偶數(shù)堂,片b為矛奇數(shù)將,披gc開(kāi)d(捷a,山b)抖=g域cd橫(a飽/2駕,b貧)如果斗a和之b均鄰為奇騾數(shù),另g戰(zhàn)cd竭(a壤,b棟)=簡(jiǎn)gc調(diào)d(坐a-山b,訂b)不需茄要除晶法,閥適天合大傘整數(shù)擴(kuò)展咽問(wèn)題一定敢存在蒼整數(shù)疫x,養(yǎng)y，盲使得五ax總+b夾y=妄gc額d(膏a,脊b)in斗t離gc涂d(味in時(shí)t也a,敲i紋nt鬧b恢,自in誤t&鋪x,千i絮nt搖&絡(luò)y)蝕{if疊(!極b)漫{理x熊=歲1;灶y昨=推0醒;炮re寶tu圾rn宏a謊;班}el敏se疑{選in量t購(gòu)r代=讓gc禁d(沒(méi)b,床a酸%b桿,愧x,給y衡);t盈=隊(duì)x;止x向=競(jìng)y斯;瓜y飽=城t劉–凱a/亂b*麥y(cè);re賺tu暢rn墓r老;追}}由數(shù)存學(xué)歸好納法垃可證錘明a改x+粒by季=g國(guó)cd渣(a倉(cāng),b崖)滿足ax+by=d的數(shù)濁對(duì)(x,y)不否是惟奏一的店,辮因?yàn)槌僧?dāng)x增加b且y減少a時(shí)和宜不變輪。例題薦：除架法表閥達(dá)式除法娘表達(dá)底式有圈如下惡的形偽式：X1/X2/X3/現(xiàn)…可/Xk其中Xi是正沸整數(shù)缺且Xi≤1嚴(yán)09(k≤1婆0,術(shù)00嫩0)靜。除法盜表達(dá)傭式應(yīng)走當(dāng)按饑照從彩左到躲右的阿順序仍求和暫，例舊如表字達(dá)式候1/航2/扮1/狠2的父值為綿1/齊4。蔬可以宅在表頂達(dá)式撤中嵌壤入括暴號(hào)以窄改變色計(jì)算樸順序間，例掌如表途達(dá)式梳(1趙/召2悉)葛/貝(1陸/圖2無(wú))的決值為唐1。現(xiàn)在從給一籮個(gè)除削法表衫達(dá)式E要求盜告訴甚是否豈可以漂通過(guò)侮增加份括號(hào)北使表液達(dá)式原值為危整數(shù)趣。分析X2礦必須睬在分匹母,島其嬌他都早可以洞在分疫子最后倡結(jié)果怖是整鴨數(shù)嗎艷？方法厭一:榨把繞X2瓣分解群因數(shù)方法裹二:題每濤次約族掉X訊2和假Xi介的最阻大公彈約數(shù)因數(shù)偷分解隊(duì)是困污難的必，因嬸此方地法二賀優(yōu)例題椅：無(wú)顆限賽墊跑AB旬總長(zhǎng)昆度為袖L車一俱從A拖出發(fā)脖，速購(gòu)度為卷u車二簽從B財(cái)出發(fā)蛇，速粗度為羅v走到雜端點(diǎn)短立刻搬返回榮，無(wú)按時(shí)間陵損失開(kāi)車閣總時(shí)株間tu,博v糟,屯t都跌是正伴整數(shù)相遇杜多少終次？分析第一盞種相訓(xùn)遇:摩相酷向t?(u+v)=薦(2k+1慚)L第二敘種相含遇:參同缺向t?|u?朗v|=楊(2k+1觸)L重復(fù)媽:什在端惑點(diǎn)相著遇第一娃次同法時(shí)到融達(dá)端冒點(diǎn)時(shí)旋刻為煌r到達(dá)章不同辭端點(diǎn)移?到達(dá)敵同一棍端點(diǎn)A和筋B分穿別運(yùn)跑動(dòng)2k1L和(真2k2+1柜)L下一載次到夸達(dá)哪并里?不同漸端點(diǎn)儲(chǔ)?又眼同時(shí)這到達(dá)服此端鍛點(diǎn)?鍵同時(shí)弊到達(dá)桂另一宰端點(diǎn)恩?t=(鑒2k+1搖)r分析如何守求r?r是L/u的整溫?cái)?shù)倍制(u*r=k1L)r是L/v的整懼?jǐn)?shù)倍r是L/g畫(huà)cd儉(u,v)的稀整數(shù)塞倍u/g辦cd腦(u,v)坑*r/(L/g慘cd怠(u,v))歇=k1r是滿伍足條取件的統(tǒng)最小淡正數(shù)r=L/g鋼cd待(u,v)問(wèn)題避4:擋分脊解因濃數(shù)分解擁因數(shù)約可以覽轉(zhuǎn)換怎為求鐘最小薦素因輕子(民找到吧最小窄素因久子后龜遞歸用求解弦)分解愿素因修數(shù)后鐮得到危惟一姐分解僵式s咬um釣{p襪iki},阻可鵝以求望出約滿數(shù)個(gè)疤數(shù),頂即買所有那ki+1畏的乘牧積(朱由乘節(jié)法原響理容次易證京明)方法糧一:矩試拘除法方法害二:潑p籌ol洪la所rd宗-r竿ho園算法思考形：反跳素?cái)?shù)正整寒?dāng)?shù)n雷是一炒個(gè)反男素?cái)?shù)謝，如難果這縱個(gè)數(shù)貫的約篇數(shù)個(gè)膠數(shù)超干過(guò)比銹n小耍的任原何數(shù)寄的約棉數(shù)個(gè)斗數(shù)。給定郵n(貪<=僚2*偉109)，萄求不誤超過(guò)攀n的司最大笑反素業(yè)數(shù)數(shù)捏m二、包進(jìn)位陣制例題吹：集成裝箱用若族干個(gè)什盒子絕（盒仿子的間高度拘為2做的非吹負(fù)次新冪）境填滿資若干趙個(gè)集啞裝箱紹（高悟度也刮是2機(jī)的非搬負(fù)次害冪）贏，使距所有堵盒子傳的價(jià)黎值和欲最小考。盒子疏和集氧裝箱縮慧的底勤面全但等，強(qiáng)因此巨只需妹要考筒慮高垂度分析對(duì)于碗每個(gè)艷尺寸電的盒帖子，臟按照蜻價(jià)值幸從小昨到大永排序填充輔a的賺尺寸為為0邪的集槽裝箱榜時(shí)只匪能用膝尺寸懼為0膜的盒訊子，晴取最妹小的哭a個(gè)診，剩雨下的在兩兩北組合拋供填山充尺戀寸為鄙1的毫集裝多箱時(shí)申使用當(dāng)需病要填首充a宏個(gè)尺謹(jǐn)寸為怎k的爸集裝聲箱時(shí)天，選臨擇尺磨寸為淡k的沙盒子塘中價(jià)圓值最淺小的臭a的焰，然盾后把狠剩下掠的兩兩闖組合規(guī)成尺緣瑞寸為搏k+嚴(yán)1的供宋下一桌次選冬用時(shí)間屢復(fù)雜對(duì)度：舉O(趙n)例題桐：反蝦轉(zhuǎn)TO絞M有堂9個(gè)久寄存擱器a隱[1爪].丸.a敗[9濫]，臟支持烏以下臘操作S躁i艷j,趁a被[j運(yùn)]a[尚i]咸+1扶(綁i可催能等天于隸j)P懇i,譯輸健出a障[i杏]任務(wù)蠢:軟對(duì)于考給定抹n<乘=2引55虛，設(shè)浮計(jì)各緊個(gè)寄數(shù)存器太的初咸值和脈一個(gè)菠TO因M程恢序，住按順谷序輸發(fā)出講n,扇n辯-1麻,爺n-東2,瞇…頭0最長(zhǎng)槐的“胳連續(xù)初S操距作”投片段日長(zhǎng)度問(wèn)P應(yīng)蹈盡量序小算法些一寄存相器i踏(i運(yùn)<=羨8)誰(shuí)負(fù)責(zé)秀輸出智最右荷的非凝零位污為第就i位豈的數(shù)初始廈時(shí)設(shè)損置每傳個(gè)寄肚存器回為此刑類數(shù)信的最絮大值裹，寄噴存器相1-閥8依帶次為挽12蘆8,計(jì)1事92享,弄22括4,毒2用40義,班24往8,拴2過(guò)52漢,拾25筍4,第2衰55咐，寄錄存器的9保陳持0輸出似24決8(有11鞭11100圣0)曲后，疊應(yīng)準(zhǔn)綢備2蠢32蜜(1供11馳0100刪0)設(shè)置券連續(xù)妄S操字作個(gè)俯數(shù)的旅限制設(shè)P，侄每次峽準(zhǔn)備傅好一費(fèi)個(gè)數(shù)成后如侄果P循限制同還未騎達(dá)到訊，應(yīng)健該繼松續(xù)準(zhǔn)橋備后玩面的乞數(shù)，噸而不牌要急剝著輸環(huán)出對(duì)于叮n<稈=2盾55議，P滋限制休不大萄于4算法竊二基本勝思想懂：剛影執(zhí)行駁輸出槐指令昨的寄拾存器壞馬上恩改考慮次4個(gè)安寄存媽器的故情形為，下柏劃線姿是輸吳出值N,耀N-詢2,淋N吵-5役,天N-炊9N-梁1,愚N-喉2,可N激-5濾,楚N-端9N-邀4,N-鳴2,限N-黎5,填N壤-9N-叛4,N-演3,黨N-養(yǎng)5,述N顫-9N-販4,叔N-片8,晃N認(rèn)-5揭,網(wǎng)N-曾9N-丹7,吃N坐-8穩(wěn),N-疏5,夾N-底9N-昨7,眉N纏-8律,N-艙6,余N-駕9推廣姜到9論的寄詞存器綿，對(duì)彈于N帳<=烈44然，可伙得到攜P=艷1的沒(méi)解例題俯：奇綠怪的貫計(jì)數(shù)懷器用如希下方聲式表模示數(shù)氣：AN-含1*2N-那1+AN-儲(chǔ)2*2N-險(xiǎn)2+請(qǐng)..借.蛛+A1×2虜+A0每個(gè)條A在涼范圍傭0~超2內(nèi)叉。初始杠時(shí)所李有的囑A均鋪為0恒，要杰處理慶M次憐加2x的操齡作（鼓每個(gè)吊x不戰(zhàn)一定淋都相強(qiáng)同）霜，每租次最周多只扒允許武修改滑4個(gè)銜A的織內(nèi)容窩。要求鄭模擬應(yīng)這一發(fā)過(guò)程袋。分析多個(gè)歐2連販在一漢起比膛較“音危險(xiǎn)壞”，括容易鑄超過(guò)年4次涌的限刮額讓它錢們之躍間存泄在一扮個(gè)0指，就遷緩解遮了壓京力考慮牢這樣磁的限右制條在件任意些兩個(gè)理相鄰?fù)甑?呆之間莖至少圣有一塞個(gè)0從最截低一短位2葵向更驅(qū)低的臺(tái)位數(shù)為找，伯也至某少能艇找到孝一個(gè)繁0限制游條件套避免斃了一次涌操作飄需要息影響宇O(N)個(gè)腐二進(jìn)敗制位的退劃化情泊況，魔類似迫于在藏排序攀二叉至樹(shù)中吵加入果了“船平衡腎因子脹”這霸個(gè)限功制。姑因此柳不妨臉?lè)Q這禮個(gè)限運(yùn)制條彼件為季“平膀衡性矛質(zhì)”片。分析一開(kāi)范始的虧0序佩列滿疼足平匹衡性泡質(zhì)，帖因此焦需要忌構(gòu)造鉛從一辜個(gè)平法衡狀徒態(tài)到掉另一難個(gè)平偶衡狀侵態(tài)的過(guò)渡燙法則對(duì)于鹿增加汽2i，考貨察第猴i位撕：0，特那么奪0-槍>1弱，考喬慮這漢個(gè)0播所在攜的兩留個(gè)2籠之間級(jí)的區(qū)妄間，瓦如果俱剩下腹的都醫(yī)是1菊（沒(méi)乞有0棍），趨那么鴨把區(qū)慢間最音左邊耀的2瞎進(jìn)位1，械那么訊1-榮>0那，向墾前一偷位進(jìn)座1，灑如果婦前一生位變戰(zhàn)成2肉，注僑意前禍一位姑的前賣面的胳區(qū)間頌是否屈全部神都是夜1，梢如果愚那樣慮也要研和1內(nèi))一塞樣修乎改;責(zé)如佩果前想一位毯原來(lái)混就是蚊2，壘那么吼跳轉(zhuǎn)嘴3)2，拖那么誤2-艇>1俱，再橫將其這前面絨一位也加1動(dòng)即可思考霧：天夜平有一疼些砝任碼,吩重鍋量為敵1,咱3砌,眉9,服2歷7,飼8替1…柱形如駝3k名,菊每個(gè)捎重量畜砝碼顯只有躲一個(gè)抵.基任意健給一艱個(gè)重盤(pán)量為鳥(niǎo)m的押物體揭,暮把它面放在澤天平庸左邊論,瀉如何儉把放崇置砝往碼使兆得天盞平平扇衡?眠放淚在左咬邊或物者右譯邊都盈可m<粉=1路010清0思考播：9稍87肺65沒(méi)43敢21拍問(wèn)題求有賢多少澡個(gè)n位數(shù)濕平方秋以后恐的末而9位繳為9浸87胡65遙43奴21樂(lè)。思考訴：奇估妙的犁數(shù)給定奶n,陶m駝，尋配找m集位n臂進(jìn)制淡數(shù)A桑，使喂得2葉A，垮3A萬(wàn)，…摘mA充的數(shù)郵字均闊為A挽數(shù)字蹲的排舟列如m番=6拴,效n=清10僻時(shí)，訴14訂2,睬85公7是答唯一登解給定督數(shù)據(jù)餅最多誼只有竄一組懂解，賊也可鍬能無(wú)年解（慌如m塞=6蹲,來(lái)n=凈10鑒0時(shí)杯）三、猴模算扶術(shù)與稍方程歐拉際定理歐拉所函數(shù)奇:充1~解n中蘿和n柱互素蠅的元登素個(gè)抵?jǐn)?shù)(n)Eu侍le旅r定棍理若g彼cd黃(a,n)=鍛1則a(n)1浴(m殃odn)意義藝：當(dāng)挨b很博大時(shí)衣abab擋mo醒d較(n)(m雕od臘n昆)，皮讓指示數(shù)一歐直比樸較小歐拉伶函數(shù)送是積翠性函拿數(shù)，旬即當(dāng)吩(m考,n膀)=肉1時(shí)扁f(贊mn牛)=利f(惕m)張*f烤(n朝)思考抹：歐碰拉函扯數(shù)的鼠計(jì)算給定但n，搶需要遠(yuǎn)多少引時(shí)間繼計(jì)算(n)？給定影n，知需要純多少循時(shí)間炕計(jì)算(1慰),(2宋),亞…樂(lè),(n)的榴所有善值？例題斗：模乏取冪a,p,m,n均為枝正整戚數(shù)，a,p為素秘?cái)?shù)1攝<a,p,m,n<65席53挺5，登且n2a,n2p。求勵(lì)：如a=3才27蘋(píng)19煌,p=5霧43燙23診,m=9木9,n=6專53件99抖，則抓結(jié)果流為4亂61廁84例題裕：模粱取冪記f(a,p,m,n)為杏本題費(fèi)所求厚的數(shù)悔，n=1成時(shí)，哲任何勾數(shù)模n都是哈0，紫所以f(a,p,m,n)=駝0，牛否則a=1湊時(shí)，a的任施何次昂冪都展是1屑，結(jié)李果為鄉(xiāng)豐1梢mo嶺dn；否唇則m=0饞時(shí)，爽結(jié)果猛為=amo云dn；否捉則n=a時(shí)，a的次卡冪永席遠(yuǎn)是n的倍腫數(shù)，蓬結(jié)果旦為0浩；否飄則n=2a時(shí)，約因?yàn)閍,p2，閥如果a中有應(yīng)2的襖因子煮，則a的次雜冪永館遠(yuǎn)是n的倍噸數(shù)，蠅結(jié)果艇為0擁，否疼則為a；否埋則a,n互素界，f(a,p,m,n)=af(p,p,m-1起,(n))mo金d準(zhǔn)n，年問(wèn)題淹轉(zhuǎn)變刺成求akmo屑dn，可波以二銹分求罰解線性腫同余紡方程ax≡b(m誕odn)方法鑼一：震利用哥Eu虹le趟r函鄭數(shù)a*a(n)-及11a(b*a(n)-脹1)b關(guān)鍵首:聯(lián)求abmo降d例na,a2,a4,a8,a16,回…同余朗方程揮可以蝴做乘屋法，矩b做因二進(jìn)隙制展隨開(kāi)選時(shí)擇方法荷二：肺擴(kuò)展斬的E帥uc謊li洲d算第法存在防整數(shù)y，使側(cè)得ax-ny=b記d脆=(偶a,案n)集，a則’=眨a/耐d,續(xù)n蜂’=蟲(chóng)n/托d，矩必須索有d蒸|ba’英x-言n’怨y=盒1*鍋(b哲/d革)注意萌：x草不唯秀一,泥所景有x倉(cāng)相差蠶n/配d的絞整數(shù)臉倍中國(guó)女剩余就定理考慮甩方程大組x≡ai(m鉗odmi),串mi兩兩融互素在0傻<=箭x<揉M=豪m(xù)1m2…mk內(nèi)有侄唯一棗解記Mi=M羽/mi，則符(Mi,mi)=納1存在壩pi,qi，Mipi+miqi=1記錄眉ei=Mipi，則j=窄i時(shí)除ei≡1軌(m黨od血mj)j<蓬>i端時(shí)ei≡0顫(m修od發(fā)mj)則e1a1+e2a2+…黃+ekak就是匹一個(gè)糧解,肯調(diào)衫整得稿到[河0,掠m)姜內(nèi)的喜唯一叨解（穩(wěn)想一醒想，共如何深調(diào)整肆）整理抄一下一般肅線性獵方程模組aixi≡bi(m名odni)ax≡b(m觀odn)x≡b1(m朽odn1)x≡b1(m討odn1)x≡b1(m鉤odp1,i)用中寇國(guó)剩寒余定丙理其他商規(guī)則給同余賀方程二項(xiàng)矛方程餓:咽借助舉離散表對(duì)數(shù)問(wèn)(本退身?幸?)高次效方程礦:疤分解覽n,毅降踢冪單個(gè)麥多變件元線高性方祖程:習(xí)消幼法例題坐：整穴數(shù)序湊列已知矮{A1,…蠅,An}、健B、藏P求畢{X1,…賭,Xn}使紙得A1X1+…屋+AnXn=呼B(殘mo速d咐P)分析設(shè)g薦=(怒A1,A2,…乏An,P先)，砍若g晃不整梨除B準(zhǔn)則無(wú)普解，縱否則秀我們習(xí)可以闖用遞江歸構(gòu)滴造解曬：將A1,…喇An、P糕和B律全部節(jié)除以讓g，挺此時(shí)矩((芒A1,…蹈An),蒼P)遞=1賊，若n祥=1裂，則遭直接間求X1使得術(shù)A1X1mo乒d濁P=甜B(yǎng)；拉否則設(shè)(蒸A1,…京,An-盒1)=略D，漸則根役據(jù)歐則幾里語(yǔ)德算尤法一俘定存蓮在x盆和y莖使得倉(cāng)ANx鴿+府Dy蠢=壞B篇(m橋od叔p病)，形可以策令Xn=x羅,膊則羨A1X1+…久+An-找1Xn-刑1=B賢-AnX=寬Dy膝(m皺od沾p趕)分析(A1,…敞,An-析1)=兆D,憑所嚇以(似A1,…脂,An-謀1,P圾)遭=皇(D猛,P堅(jiān))懂|呼(D嗎y話mo盾d首P)散,去因此拐完全垃轉(zhuǎn)化團(tuán)為n拐-1懂的情襪形,命令僵B=沖DY戀m米o(hù)d駁P窩即可四、氣雜題例題尿：F束er理ma哈t很vs燦P領(lǐng)yt天ha鉆go售ra微s給N虧(<呢=1世00有,0鬼00舒)，丟考慮拴滿足士x2+y2=z2(x援<y肅<z桃<=拼N)愚的三扇元組求x遭、y下、z脾互質(zhì)售的三稼元組宋的個(gè)灰數(shù)和抓不屬?gòu)?qiáng)于任蛇何三竊元組略(不鬼光是充互質(zhì)晌)的箱k(他k<屈=N佩)的鋤個(gè)數(shù)圈.例(輸入:輸出)10預(yù):固1谷425犁:予4菊910賤0:蘇1炎6移27分析本原激三元鵲組一慕定可偷以寫(xiě)崖成x折=u久v,裹y廣=u2-v2,糧z童=u2+v2,晝其中嚴(yán)u,氣v厚互質(zhì)其他久是本寄原三始元組怪的整論數(shù)倍算法預(yù)處崇理,屬保襪存1臉00曠,0變00容內(nèi)的杠所有窯本原檔三元咐組,遭以破z為壘關(guān)鍵妻字排站序,是d插[i近]為卷z<抗=i越的個(gè)姨數(shù),年遞扛推標(biāo)記疼它們蛇的倍釣數(shù)涉棟及到汁的數(shù)慌,茶按序缺遞推像不屬釣于任拒意三醋元組惰的個(gè)塘數(shù)g門(mén)[i螺]回答庸詢問(wèn)器是O蹄(1乒)的貧,鴉空間化O(巾n)例題葡：沒(méi)答有矩真形n*鏈n的鑼網(wǎng)格蘭,軍要求齊每行棗每列壯恰好宅k個(gè)爬黑點(diǎn)亦，但積任意遠(yuǎn)四個(gè)水黑點(diǎn)豪不構(gòu)躬成矩憤形輸入愛(ài)k,纖求補(bǔ)n=擇k2-k安+1眼的一敘個(gè)解k<虧=3扎2且每k-呈1為奇0,挽1寨或素虛數(shù)分析每行挪用k巡壽個(gè)數(shù)仔表示禮黑色丘點(diǎn)的旗列編員號(hào),下則宣不存喇在矩健形當(dāng)副且僅庫(kù)當(dāng)任假兩行狡最多縫一個(gè)缺相同絹數(shù)構(gòu)造宗法.第1房誠(chéng)行涂確點(diǎn)1膨,考2,志3導(dǎo)…k以下虎分k遵個(gè)塊鏟,零每塊撿有k能-1時(shí)行,乏共踢k2-k援+1申行第i啟個(gè)塊炎的一榨個(gè)點(diǎn)廁均為字i第一牧個(gè)塊樸的其迎他點(diǎn)跪?yàn)閗嘗+1啄~k2-k墻+1其他驕每個(gè)年塊的絲式各行王為第迷1個(gè)挪塊的衰一個(gè)平移竄覆蓋以k企=6略為例腔,位第1旅行和癥第1哄個(gè)塊福(共嶼6行拒)為脂:1招2被3給4截5明617鋪8校9起10疤1宰1112番1歡3漆14奮1筒5舞16117飲1您8議19樹(shù)2忠0喊21122麥2犬3溜24鉛2保5去26127販2頌8疼29賽3牢0黑31以k賤=6終為例第一魔行為難1~印k,驗(yàn)即范1~喪6每個(gè)蜂塊有陣k-衰1行粘,跟即5飽行第i塘個(gè)塊從的第冊(cè)一個(gè)鹿數(shù)均炎為i第1距個(gè)塊李的其蛙他點(diǎn)冤為k洗+1潮~k2-k作+1掏即7園~3址1下面搭開(kāi)始摔一行旁一行辨構(gòu)造執(zhí)第2騎個(gè)塊1庸2莖3島4安5猶6178辭9類1慢0鞋111嫩12夢(mèng)1誕31415寺1全61頑17丘1駕8黑19伏2律0211壞222324拆2頂5溫261茂27叨2告8麥29303127息14汽2典1備23泉3勁0第1沾個(gè)數(shù)怠總是贏2第2匙從第別