劉汝佳數(shù)論初步

2005年浙江省隊培訓

第1講數(shù)論初步劉汝佳目錄一、基本概念二、進位制三、模算術與方程四、雜題一、基本概念基本概念整除與約數(shù)、倍數(shù).注意負數(shù)可整除性的基本性質(zhì)若a|b,a|c,則a|(b+c)若a|b,那么對所有整數(shù)c,a|bc若a|b,b|c,則a|c整除關系具有傳遞性.它是偏序關系(partialorder),<|,Z>是一個格素數(shù)和合數(shù)如果大于1的正整數(shù)p僅有的正因子是1和p,則稱p為素數(shù)(prime)大于1又不是素數(shù)的正整數(shù)稱為合數(shù)(compound)如果n是合數(shù),則n必有一個小于或等于n1/2的素因子算術基本定理每個正整數(shù)都可以惟一地表示成素數(shù)的乘積，其中素數(shù)因子從小到大依次出現(xiàn)（這里的“乘積”可以有0個、1個或多個素因子）。換句話說,任意正整數(shù)n可以寫成n=2a1*3a2*5a3*…,其中a1,a2,a3等為非負整數(shù)這個定理也叫做惟一分解定理。它是一個定理而不是公理！雖然在大多人看來，它是“顯然成立”的，但它的確是需要證明的定理除法和同余令a為整數(shù)，d為正整數(shù)，那么有惟一的整數(shù)q和r，其中0≤r<d，使得a=dq+r可以用這個定理來定義除法：d叫除數(shù)，a叫被除數(shù)，q叫商，r叫余數(shù)。如果兩個數(shù)a,b除以一個數(shù)c的余數(shù)相等，說a和b關于模c同余，記作a≡b(modc)同余為什么有同余?13241234…1+432435..2=24….7余數(shù)可以作為原數(shù)的一個signature(標記).如果標記下的運算錯誤,一定錯誤如果標記下的運算正確?最大公約數(shù)和最小公倍數(shù)令a和b是不全為0的兩個整數(shù)，能使d|a和d|b的最大整數(shù)稱為a和b的最大公約數(shù)，用gcd(a,b)表示，或者記為(a,b)。令a和b是不全為0的兩個整數(shù)，能使a|d和b|d的最小整數(shù)稱為a和b的最小公倍數(shù)，用lcm(a,b)表示，或者記為[a,b]定理:ab=gcd(a,b)*lcm(a,b)定理的證明使用惟一分解定理.設則有:容易驗證定理成立例題：佳佳的困惑給出一個數(shù)N，含數(shù)字1、2、3、4，把N的所有數(shù)字重新排列一下組成一個新數(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互素,因此要么k是完全平方數(shù)要么k/2是完全平方數(shù)分別設k=m2和2m2,枚舉m例題：齒輪假設有三種齒輪：6齒，12齒，30齒。想要實現(xiàn)4:5的比例，一種可行方案如下：給定可用的齒輪（每種均有無窮多），設計一系列傳輸c1:d1,c2:d2,…,cm:dm，使得其綜合比例(c1c2c3…cm)/(d1d2d3…dm)為給定值a:b。給定齒輪的齒數(shù)為5到100，a和b不超過10000。分析使用愁惟一船分解憲定理,單獨麥考慮荷各個義素因章子c1胡=碼p傾1a1*p因2*a2*…c2覽=省p席1b1*p練2*b2*……則c1x*c2y=p些1(x騾*a燥1+絲式y(tǒng)*凈b1果)*p榜2(x*a2質(zhì)+y棕*b寇2)目標a:躺b=津p1z1*務p2z2…x*a勻1+y*b厘1=真z1幣;鏟x*鳴a2啄+y倦*b所2=熟z2分析第i個齒汪輪的湖使用拔情況恥用xi表示演，xi>0表示配用在廢分子xi次，xi<0表示坦用在足分母-xi次。由于ai<=怠10天0，只斬需要抱考慮10臂0以內(nèi)產(chǎn)的25個素賄數(shù)考慮茅每個友素數(shù)pi的指油數(shù)，因可以吵構(gòu)造哨一個億線性未方程宅，共25個等餓式分子街分母叨個數(shù)姑相等塞，故每所有xi的和對為0，消元希后枚妖舉獨藥立變豪量例題歡：破污解RS阿A給定M個數(shù)身，它期們的戚質(zhì)因蠟子在訴前T個質(zhì)倍數(shù)范究圍內(nèi)柿。求很這M個數(shù)斃組成遮集合鍬的滿級足如巾下條季件的簽非空則子集謠個數(shù)念：子責集中瘡所有閉數(shù)的遮積為麗完全為平方耗數(shù)。分析首先抹將讀狼入的M個數(shù)諷，分宇解質(zhì)燥因數(shù)壟，并讀對每吃個質(zhì)培因數(shù)蘆出現(xiàn)恐次數(shù)謊的奇溝偶性徑進行參記錄咬。設x[計i]=牌0或1代表肢是否育使用恐第i個數(shù)馳?？梢埔粤徐F出一奴個關荷于x[麥i]寫(1消<=阿i<膀=m艷)的位鹿方程虛組（嬌乘積凝的所雕有質(zhì)牌因數(shù)麥出現(xiàn)書次數(shù)廚均為眾偶數(shù)餐）。解該鄉(xiāng)豐方程表組，常檢查隊最后鬧有多去少自憐變量芳，設沈有n個，除那么床結(jié)果窗應該糊是2n巡壽-1（除夠去空阿集）青。惜時空捷復雜螺度均亞為O(葬M2)思考適：傳菌球游桐戲N個人贈圍圈辟玩?zhèn)鳑r球游吹戲，雜開始晝時第蒙一個靜人拿汽著球妹，每乏個人獄把球螺傳給態(tài)左手沃的第K個人嬌。滿切足1≤們K≤銜N/續(xù)2。求K的最盟大值跪，使館得第層一個趙人重接新拿蟻到球校之前食，每綁個人其都拿洽過球貪。基本謙問題如何背求1~蒜n的所分有素歇數(shù)?如何曉判斷毯一個辰數(shù)n是否振為素王數(shù)?如何壟求兩抬個數(shù)泉的最物大公慘約數(shù)?如何膀給一愉個數(shù)n分解鄰素因都數(shù)?問題1:乘1旅~n的素菜數(shù)假設農(nóng)要求1~疊10潔0的素厭數(shù)2是素望數(shù),刪除2*備2,刷2僚*3饞,蹈2*技4,糠…綁,忽2*湊50第一畏個沒聽被刪合除的序是3,刪除3*秒3,蛋3域*4鏡,鞋3*奇5,俘…,霸3*循33第一應個沒潛被刪版除的研是5,刪除5*恩5,逼5姐*6兵,獄…翅5*穩(wěn)20得到所素數(shù)p時,需要病刪除p*漫p,詠p診*(款p+陜1)倉,狂…贏p*瞧[n/側(cè)p],運算趴量為[n/鎖p]針-p,其中p不超桑過n1/呆2(想一顆想,為什公么)Er懂a(chǎn)t妨os橫th洋en沾es的篩判子小知鑼識(ma迫th叉wo潮rl誓d.迷wo進lf狐ra削m.蘭co挨m)近似徐公式(Le浸ge財nd秋re常數(shù)B=封-1屬.0腐83購66服)思考題：正冠多邊夫形給圓釋周上n個點婚的坐氧標,能組擋成多奶少個到正多奧邊形余？問題2:素數(shù)油判定枚舉肢法:灰O(裕n1/糠2),指數(shù)留級別改進待的枚訪舉法:絮O(偏ph酒i(寶n1/洞2))壺=O馬(n1/判2/l殿og繡n)型,仍然寬是指榜數(shù)級春別概率預算法:礎Mi往ll享er基-R叼ab踩in測試+癢Lu漁ca烈s-Le吼hm坡er測試Mi即ll構(gòu)er或-R矛ab筋in測試對于慈奇數(shù)n,記n=呆2r*s頑+1盾,其中s為奇演數(shù)隨機憑選a(啞1<撇=a暮<=己n-胖1)侵,琴n通過踏測試暮的條極件是as≡1間(m短od唇n敵),或者存在0<哪=j譜<=器r-莊1使得a2^蔥j*老s≡-棕1(誼mo殘d起n)素數(shù)額對于尚所有a通過懼測試,合數(shù)構(gòu)通過受測試暮的概貞率不儉超過1/域4只測缺試a=棄2,研3蛋,融5,為7賀,則2.百5*爭1013以內(nèi)班唯一躍一個艙可以翠通過糠所有貢測試寧的數(shù)五為32橋15縮慧03舞17姓51思考京：區(qū)店間內(nèi)倉的素訓數(shù)給出n,m(蹄n<=盯106,留m<杏=1怒05),求n~轎n+綱m之間就的素詢數(shù)有去多少由個哪種絞方法漏快?篩還裳是依躲次素趟數(shù)判恩定?問題3:最大珠公約梁數(shù)方法錯一:使用占惟一大分解喜定理,先分鬧解素級因數(shù),然后厭求最瀉大公憑約數(shù)方法狀二:砍(E熱uc躬li樣d算法)利用悲公式gc且d(鬼a,鼻b)埋=gc沃d(斯b,羨a絮mo袖d狹b)抓,時間垃復雜疫度為O(清lo爬gb)方法德三:孫(二進逢制算種法)若a=也b,gc網(wǎng)d(嶺a,誘b)=跡a,否則A和b均為歉偶數(shù),gc軍d(江a,友b)=透2*德gc胃d(詳a/昏2,脖b/仇2)A為偶晶數(shù),津b為奇跑數(shù),gc庫d(堅a,匪b)=古gc案d(律a/析2,針b)如果a和b均為桌奇數(shù),gc型d(眠a,番b)=gc重d(照a-惕b,義b)不需覆要除礎法,適合開大整頓數(shù)擴展話問題一定暖存在遠整數(shù)x,赴y，使敵得ax事+b邪y=gc摧d(些a,猜b)in勺tgc劉d(繞in匪ta,in暢tb,in色t&里x,in艦t&控y)孫{if脅(!敢b){遵x繞=愚1背;農(nóng)y肢=秧0;潑r鉤et倉ur價n套a;膏}el紹se否{in乘tr糖=gc番d(朱b,a%作b,蹲x,橋y附);t山=啞x;糠x奔=柏y旱;螞y鋪=開t跟–挑a/置b*售y;re設tu里rn的r噸;橫}}由數(shù)生學歸飼納法刪可證喂明ax業(yè)+b妻y=gc拴d(糟a,條b)滿足ax+by=d的數(shù)圖對(x,y)不是抗惟一熄的,因為恢當x增加b且y減少a時和芽不變膽。例題頁：除高法表齊達式除法鳥表達肥式有抱如下選的形秧式：X1/X2/X3/盜…磚/Xk其中Xi是正卻整數(shù)芹且Xi≤1唯09(k≤1顯0,坑00備0)。除法牲表達乘式應速當按怨照從要左到還右的療順序胳求和斜，例廊如表豬達式1/于2/鞠1/僑2的值沸為1/爹4?？缮煲栽诒急磉_糾式中悠嵌入首括號熟以改失變計秩算順掛序，療例如羞表達肯式(1筍/頸2享)猴/造(1間/異2互)的值墳為1?，F(xiàn)在戶給一幟個除注法表嘗達式E要求禁告訴斬是否妻可以縱通過標增加砌括號律使表能達式街值為飛整數(shù)丈。分析X2必須仁在分監(jiān)母,其他徹都可具以在嚇分子最后屢結(jié)果屠是整粥數(shù)嗎凳？方法暈一:把X2分解逼因數(shù)方法板二:每次危約掉X2和Xi的最孫大公乒約數(shù)因數(shù)羽分解揮是困魯難的震，因屯此方危法二街優(yōu)例題替：無釣限賽囑跑AB總長客度為L車一右從A出發(fā)臣，速鋪度為u車二元從B出發(fā)誦，速攤度為v走到設端點雕立刻惜返回遍，無佳時間兆損失開車油總時城間tu,滑v藥,儲t都是展正整臂數(shù)相遇橋多少裹次？分析第一響種相搬遇:相向t?(u+v)=脖(2k+1虎)L第二門種相澆遇:同向t?|u?釘v|=殃(2k+1丟)L重復:在端最點相釋遇第一裁次同剃時到收達端黑點時晴刻為r到達跳不同疏端點?到達奴同一蕉端點A和B分別伍運動2k1L和(2k2+1詠)L下一花次到可達哪和里?不同趣端點?又同蜻時到鏟達此傍端點?同時壩到達形另一池端點?t=(棒2k+1感)r分析如何乒求r?r是L/u的整利數(shù)倍(u*r=k1L)r是L/v的整懼數(shù)倍r是L/gc隆d(u,v)的整丑數(shù)倍u/g遠cd諸(u,v)旗*r/(L/g匠cd彼(u,v))彈=k1r是滿音足條謝件的哀最小疾正數(shù)r=L/gc默d(u,v)問題4:分解托因數(shù)分解喇因數(shù)早可以睛轉(zhuǎn)換挽為求賊最小抬素因租子(找到已最小祖素因勇子后純遞歸朗求解)分解碧素因誼數(shù)后漁得到倒惟一籠分解臺式su盒m{依piki},可以經(jīng)求出戀約數(shù)缺個數(shù),即所息有ki+1的乘呼積(由乘變法原鋼理容胸易證鮮明)方法誤一:試除則法方法嫂二:失po島ll終ar財d-rh郊o算法思考撐：反識素數(shù)正整爛數(shù)n是一浴個反僅素數(shù)麗，如嚇果這嘗個數(shù)卸的約朗數(shù)個聯(lián)數(shù)超說過比n小的坦任何梯數(shù)的霸約數(shù)谷個數(shù)搭。給定n(鼻<=您2*懷109)，求非不超可過n的最兇大反纏素數(shù)史數(shù)m二、蓮進位遞制例題音：集稅裝箱用若擊干個砌盒子喊（盒苦子的臭高度候為2的非描負次魚冪）謀填滿妄若干儲個集齡裝箱油（高舞度也螺是2的非謀負次修冪）任，使臺所有匹盒子穿的價葵值和泡最小都。盒子佛和集攤裝箱停的底但面全焰等，勿因此毯只需危要考怎慮高鞋度分析對于糊每個昌尺寸呈的盒宴子，榴按照認價值糟從小每到大色排序填充a的尺坐寸為0的集漫裝箱鞋時只皂能用投尺寸伐為0的盒陡子，由取最班小的a個，騙剩下蘆的兩鋸兩組艘合供耍填充層尺寸籃為1的集猜裝箱元時使控用當需崗要填討充a個尺蝕寸為k的集截裝箱撥時，女選擇壓尺寸鐵為k的盒鎮(zhèn)子中愧價值刊最小返的a的，胸然后文把剩管下的兩兩則組合露成尺缺寸為k+眨1的供商下一攝次選傭用時間役復雜岡度：O(箱n)例題虛：反富轉(zhuǎn)TO軋M有9個寄倍存器a[身1]遍..軟a[硬9]，支懼持以講下操蹤蝶作S嘉i辰j,騙a亡[j戒]a[駛i]俊+1綿(浸i可能休等于j)P湯i,輸出a[戀i]任務:對于稈給定n<甲=2抵55，設嶄計各呢個寄救存器肆的初秩值和立一個TO鬼M程序核，按痕順序欲輸出n,農(nóng)n禍-1因,傾n-妥2,羅…循0最長坐的“蜂連續(xù)S操作錦”片繞段長遠度P應盡第量小算法學一寄存遵器i(喜i<=物8)負責絲式輸出軟最右床的非華零位榴為第i位的私數(shù)初始尚時設柄置每秤個寄緩存器摔為此勞類數(shù)循的最寄大值辰，寄左存器1-脊8依次過為12循8,東1表92育,夜22巡壽4,槳2震40右,少24置8,值2天52施,敲25作4,拆2慚55，寄堆存器9保持0輸出24垮8(釣11逮11100辨0)后，叨應準覽備23作2(堤11太10100粘0)設置堡連續(xù)S操作谷個數(shù)謀的限筆制P，每筋次準沒備好潮一個姐數(shù)后腐如果P限制喚還未漁達到稈，應悉該繼跟續(xù)準幫備后簡面的居數(shù)，渡而不盈要急叫著輸漂出對于n<既=2儉55，P限制慌不大泥于4算法健二基本交思想暑：剛型執(zhí)行波輸出淹指令叮的寄湖存器臭馬上津改考慮4個寄妖存器瓜的情鋤形，藥下劃育線是搏輸出駝值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-礦5,種N電-9N-代4,瀉N-摔8,懲N億-5太,欲N-畏9N-奶7,答N遼-8倉,N-掏5,林N-勒9N-達7,累N尋-8蔽,N-國6,拆N-掙9推廣輕到9的寄惰存器建，對序于N<沈=4蛙4，可閣得到P=豈1的解例題框：奇角怪的探計數(shù)松器用如解下方駛式表解示數(shù)爸：AN-腸1*2N-弟1+AN-礙2*2N-眠2+品..而.池+A1×2芒+A0每個A在范李圍0~放2內(nèi)。初始彩時所闖有的A均為0，要薪處理M次加2x的操訊作（臥每個x不一謝定都腹相同在），按每次呆最多壇只允倆許修哄改4個A的內(nèi)那容。要求畢模擬委這一餐過程撒。分析多個2連在軋一起耍比較宏“危驕險”嫌，容笨易超住過4次的浸限額讓它奮們之厘間存逆在一偉個0，就專緩解綱了壓鐵力考慮蒸這樣膛的限拔制條伏件任意跪兩個盒相鄰螺的2之間西至少福有一瓦個0從最獻低一擱位2向更惰低的月位數(shù)舊找，茶也至樹少能稿找到句一個0限制輕條件白避免卡了一次柄操作征需要績影響O(N)個二先進制戶位的退工化情蕉況，星類似帶于在音排序?qū)Χ嬖礃渲星蚣尤雽α恕按胶饣ㄒ蜃郁~”這穿個限墾制。書因此肝不妨獵稱這擦個限則制條匠件為雁“平蜻衡性亞質(zhì)”田。分析一開棕始的0序列膽滿足驅(qū)平衡毯性質(zhì)揪，因密此需爬要構(gòu)抽造從抵一個示平衡浮狀態(tài)喉到另命一個名平衡筆狀態(tài)贏的過渡將法則對于微增加2i，考才察第i位：0，那矛么0-勞>1，考枯慮這仙個0所在仙的兩優(yōu)個2之間設的區(qū)屯間，域如果微剩下慮的都任是1（沒伴有0），秩那么廁把區(qū)略間最宿左邊沸的2進位1，那檢么1-爆>0，向昌前一抗位進1，如漢果前腿一位概變成2，注折意前需一位孕的前攤面的忠區(qū)間奧是否意全部牲都是1，如勢果那碗樣也子要和1)一樣餐修改;如果罩前一膠位原股來就低是2，那辟么跳鈴轉(zhuǎn)3)2，那潮么2-葡>1，再圍將其叉前面士一位股加1即可思考冠：天馬平有一秧些砝帳碼,重量鞋為1,胸3救,福9,己2平7,供8鍛1…形如3k蘋,每個魯重量割砝碼遲只有避一個.任意考給一剃個重棵量為m的物宴體,把它洋放在畏天平漫左邊,如何均把放筐置砝旦碼使凈得天吩平平到衡?放在紡左邊琴或者參右邊輝都可m<湯=1訴010屯0思考棟：98仙76憤54割32息1問題求有栽多少陳個n位數(shù)朱平方油以后綁的末9位為98濃76罪54卸32疑1。思考硬：奇屈妙的誕數(shù)給定n,男m，尋編找m位n進制腰數(shù)A，使墨得2A，3A，…mA的數(shù)令字均骨為A數(shù)字躺的排樂列如m=引6,徒n坦=1營0時，14最2,濤85壩7是唯免一解給定幻玉數(shù)據(jù)勵最多脊只有偶一組缸解，印也可訴能無堅解（篇如m=映6,灘n兆=1寄00時）三、明模算殊術與桿方程歐拉賣定理歐拉袖函數(shù):蠟1~誘n中和n互素究的元駛素個膝數(shù)(n)Eu叮le蹤蝶r定理若gc恥d(a,n)=送1則a(n)1海(m軌odn)意義屬：當b很大蹲時ababmo瓣d材(n)(m茶odn)，讓屈指數(shù)估一直奮比較勿小歐拉羅函數(shù)及是積店性函腫數(shù)，羽即當(m,止n)=濟1時f(影mn)=f(腦m)*f(古n)思考甜：歐槽拉函漲數(shù)的猶計算給定n，需顯要多腫少時得間計諒算(n)？給定n，需工要多口少時殃間計嘴算(1隱),(2愚),芒…陵,(n)的所嗓有值葵？例題籌：模詢?nèi)鏰,p,m,n均為漫正整歉數(shù)，a,p為素淡數(shù)1<a,p,m,n<65戰(zhàn)53梳5，且n2a,n2p。求斯：如a=3臉27取19鍵,p=5個43摘23細,m=9視9,n=6鵝53裁99，則腫結(jié)果床為46砌18廳4例題屆：模架取冪記f(a,p,m,n)為本哭題所匠求的稱數(shù)，n=1時，序任何裕數(shù)模n都是0，所杠以f(a,p,m,n)=廊0，否核則a=1時，a的任扶何次筑冪都盞是1，結(jié)底果為1殿mo糖dn；否叉則m=0時，鐘結(jié)果幣為=amo驚dn；否疾則n=a時，a的次諷冪永謝遠是n的倍預數(shù)，疫結(jié)果曉為0；否遣則n=2a時，慈因為a,p2，如砍果a中有2的因升子，甲則a的次交冪永孟遠是n的倍淚數(shù)，商結(jié)果功為0，否頸則為a；否建則a,n互素壁，f(a,p,m,n)=af(p,p,m-1復,(n))mo圓d丘n，問宰題轉(zhuǎn)滴變成乎求akmo天dn，可趙以二剝分求丘解線性破同余翅方程ax≡b(m屈odn)方法屬一：限利用Eu拋le隔r函數(shù)a*a(n)-雙11a(b*a(n)-重1)b關鍵:求abmo均dna,a2,a4,a8,a16,躍…同余矛方程炕可以脊做乘迎法，b做二策進制俯展開傅選擇方法窄二：似擴展譜的Eu抗cl機id算法存在以整數(shù)y，使悅得ax-ny=b記d=叫(a,默n)，a’悠=a坑/d距,曲n’在=n/浩d，必康須有d|侍ba’氏x-留n’膏y=1躍*(揭b/敲d)注意雖：x不唯援一,所有x相差n/恥d的整降數(shù)倍中國浙剩余確定理考慮皇方程思組x≡ai(m柄odmi),嘩mi兩兩詢互素在0<翁=x永<M感=m1m2…mk內(nèi)有撤唯一揮解記Mi=M陸/mi，則(Mi,mi)=蔽1存在pi,qi，Mipi+miqi=1記錄ei=Mipi，則j=誕i時ei≡1枕(m真odmj)j<感>i時ei≡0質(zhì)(m燥odmj)則e1a1+e2a2+…拋+ekak就是石一個爆解,調(diào)整昏得到[0屋,m次)內(nèi)的森唯一御解（話想一胃想，膚如何牢調(diào)整擠）整理淹一下一般羞線性嚴方程惜組aixi≡bi(m虜odni)ax≡b(m糾odn)x≡b1(m距odn1)x≡b1(m腿odn1)x≡b1(m番odp1,i)用中臥國剩櫻余定棉理其他濤規(guī)則龍同余窯方程二項澤方程:借助文離散肢對數(shù)(本身??孤)高次橋方程:分解n,降冪單個元多變西元線白性方羽程:消法例題政：整捐數(shù)序雪列已知{A1,…謎,An}、B、P求{X1,…殖,Xn}使得A1X1+…資+AnXn=B(戚mo喉dP)分析設g=緞(A1,A2,…An,P)，若g不整尊除B則無復解，慕否則炸我們唐可以宇用遞絨歸構(gòu)召造解咽：將A1,…追An、P和B全部儀除以g，此喝時((邀A1,…An),坊P)=簡1，若n=垮1，則致直接觀求X1使得A1X1mo輸d異P=腫B；否病則設(A1,…牛,An-昆1)=法D，則數(shù)根據(jù)浙歐幾茫里德賣算法拔一定藝存在x和y使得ANx+Dy=B(秩mo晉dp)，可夠以令Xn=x鋒,則A1X1+…懼+An-趕1Xn-庸1=B肉-AnX=Dy乏(m韻odp)分析(A1,…赤,An-森1)=擺D,所以(A1,…稅,An-巾1,P斷)烤=飽(D獨,P逮)狡|差(Dymo也d掘P)財,因此暴完全票轉(zhuǎn)化水為n-令1的情希形,令B=懲DY圍m妖od序P即可四、憲雜題例題練：Fe幅rm峰atvsPy鵲th軍ag雀or揀as給N(其<=載10餃0,俱00城0)，考改慮滿竟足x2+y2=z2(x產(chǎn)<y級<z視<=勇N)的三綁元組求x、y、z互質(zhì)平的三棉元組怒的個后數(shù)和擔不屬舞于任伐何三賽元組(不光璃是互稀質(zhì))的k(相k<=糾N)的個艷數(shù).例(輸入:輸出)10蛇:濫1劇425誦:進4囑910余0:撒1朱6豎27分析本原磚三元陜組一棍定可控以寫舒成x=uv,呆y=吧u2-v2,填z皺=u2+v2,其中u,興v互質(zhì)其他撞是本延原三攜元組段的整竭數(shù)倍算法預處放理,保存10惹0,飼00爭0內(nèi)的膀所有模本原基三元詢組,以z為關落鍵字烏排序,d[關i]為z<絮=i的個騎數(shù),遞推標記奶它們羞的倍腫數(shù)涉找及到絹的數(shù),按序浙遞推海不屬彎于任駐意三榨元組炸的個已數(shù)g[鍵i]回答柳詢問西是O(傅1)的,空間O(麥n)例題堪：沒植有矩構(gòu)形n*凝n的網(wǎng)棋格,要求文每行敘每列盤恰好k個黑辟點，純但任討意四拘個黑與點不總構(gòu)成干矩形輸入k,求n=迎k2-k剛+1的一滑個解k<碰=3框2且k-蒙1為0,梁1或素響數(shù)分析每行淋用k個數(shù)葛表示行黑色轉(zhuǎn)點的規(guī)列編抵號,則不爆存在塞矩形標當且霜僅當悲任兩煤行最低多一專個相漆同數(shù)構(gòu)造侮法.第1行涂島點1,劃2繩,勇3…砍k以下異分k個塊,每塊聲有k-歇1行,共k2-k織+1行第i個塊紹的一乓個點港均為i第一評個塊旨的其大他點始為k+項1~視k2-k伏+1其他鍋每個逝塊的扔各行圖為第1個塊爪的一指個平移琴覆蓋以k=犯6為例,第1行和濤第1個塊(共6行)為:1準2物3喪4芹5摸617糞8徐9保10戴1蘇1112涼1拔3巷14京1芽5載16117級1巨8口19蒼2蔬0濟21122乓2租3深24帝2鋪5鐘26127捕2糧8牽29檢3胸0績31以k=遭6為例第一焰行為1~絹k,即1~距6每個鮮塊有k-娃1行,即5行第i個塊水的第如一個摘數(shù)均薯為i第1個塊秒的其某他點盲為k+范1~第k2-k籮+1即7~策31下面炮開始跌一行桌一行然構(gòu)造銷第2個塊1傳2蠻3炸4悟5膝6178筍9乒1拔0號111擋12搜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個數(shù)非總是2第2從第1個塊判復制沈來一錢個7以后辛每次屠從第1個塊捆的下齊一行貼復制,源的緞列號朵往右孝偏移21舉