noip中的數(shù)論數(shù)值問題

noip中的數(shù)論/數(shù)值問題有關(guān)數(shù)學(xué)的函數(shù)C/C++中有關(guān)數(shù)學(xué)的函數(shù)在math.h中。使用時需要注意精度問題。math.h中有個叫y0的函數(shù)，會與全局變量名沖突。log()是數(shù)學(xué)中的ln，log10()是數(shù)學(xué)中的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互質(zhì)的數(shù)的個數(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;}復(fù)雜度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}復(fù)雜度O(logn)，有非遞歸寫法，適用于高精度同余方程同余方程求關(guān)于x同余方程ax≡1(modb)的最小正整數(shù)解。ax≡1(modb)<=>ax-1≡0(modb)<=>b|(ax-1)<=>ax-1=kb<=>ax-kb=1同余方程由定理可知，ax+by=c有解當(dāng)且僅當(dāng)c|gcd(a,b)對于不定方程，一組解，設(shè)為〔x0,y0)那么通解為：x=x0+kby=y0-ka所以最終的最小整數(shù)解為(x%b+b)%b。歐幾里德擴(kuò)展定理對于不完全為0的非負(fù)整數(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下的剩余系，即如