noip中的數(shù)論數(shù)值問題_第1頁
noip中的數(shù)論數(shù)值問題_第2頁
noip中的數(shù)論數(shù)值問題_第3頁
noip中的數(shù)論數(shù)值問題_第4頁
noip中的數(shù)論數(shù)值問題_第5頁
已閱讀5頁，還剩9頁未讀， 繼續(xù)免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

noip中的數(shù)論/數(shù)值問題有關數(shù)學的函數(shù)C/C++中有關數(shù)學的函數(shù)在math.h中。使用時需要注意精度問題。math.h中有個叫y0的函數(shù)，會與全局變量名沖突。log()是數(shù)學中的ln，log10()是數(shù)學中的lg，沒有l(wèi)ogab的函數(shù)，需要用換底公式。三角函數(shù)、對數(shù)函數(shù)等很慢。盡量防止除法。double有誤差，pow(10,100)-(pow(10,100)+1)=0！二項式定理與楊輝三角最大公約數(shù)與最小公倍數(shù)最大公約數(shù)gcd(a,b)，也記為(a,b)最小公倍數(shù)lcm(a,b)gcd(a,b)=gcd(b,a%b)lcm(a,b)=ab/gcd(a,b)最大公約數(shù)與最小公倍數(shù)intgcd(inta,intb){ intr; while(b) { r=a%b; a=b; b=r; } returna;}歐拉函數(shù)小于n且與n互質的數(shù)的個數(shù)稱為歐拉函數(shù)。假設n為素數(shù)那么歐拉函數(shù)intphi(intn){ intret=n,i; for(i=2;i<=n;++i) if(n%i==0) { ret=ret*(i-1)/i; while(n%i==0) n/=i; } if(n>1) ret=ret*(n-1)/n; returnret;}復雜度O(logn)同余(a+b)%n=(a%n+b%n)%na*b%n=(a%n)*(b%n)%n快速冪intpow(inta,intn,intp){ if(!n) return1; intt=pow(a,n>>1,p); t=t*t%p; if(n&1) t=t*a%p; returnt}復雜度O(logn)，有非遞歸寫法，適用于高精度同余方程同余方程求關于x同余方程ax≡1(modb)的最小正整數(shù)解。ax≡1(modb)<=>ax-1≡0(modb)<=>b|(ax-1)<=>ax-1=kb<=>ax-kb=1同余方程由定理可知，ax+by=c有解當且僅當c|gcd(a,b)對于不定方程，一組解，設為〔x0,y0)那么通解為：x=x0+kby=y0-ka所以最終的最小整數(shù)解為(x%b+b)%b。歐幾里德擴展定理對于不完全為0的非負整數(shù)a,b那么存在唯一的整數(shù)x,y使得gcd(a,b)=ax+by。typedeflonglongll;voidexgcd(lla,llb,ll&x,ll&y){if(!b){x=1;y=0;}else{gcd(b,a%b,y,x);y-=x*(a/b);}}剩余系a(a<n)的1~n次冪模n的值稱為a在模n下的剩余系，即如

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論