noip中的數論數值

1、有關數學的函數有關數學的函數 C/C+中有關數學的函數在math.h中。 使用時需要注意精度問題。 math.h中有個叫y0的函數，會與全局變量名沖突。 log()是數學中的ln，log10()是數學中的lg，沒有l(wèi)ogab的函數，需要用換底公式。 三角函數、對數函數等很慢。 盡量避免除法。 double有誤差，pow(10,100)-(pow(10,100)+1)=0！二項式定理與楊輝三角二項式定理與楊輝三角niiniinnbaCba0)(rnrrnrbaCTmnmnmnCCC111!)!(!mmnnCmn最大公約數與最小公倍數最大公約數與最小公倍數 最大公約數gcd(a,b)，也記為(a,

2、b) 最小公倍數lcm(a,b) gcd(a,b)=gcd(b,a%b) lcm(a,b)=ab/gcd(a,b)最大公約數與最小公倍數最大公約數與最小公倍數 int gcd(int a,int b) int r;while(b)r = a % b;a = b;b = r;return a; 歐拉函數歐拉函數 小于n且與n互質的數的個數 稱為歐拉函數。 若n為素數則)(n1)( nn) 1),)(gcd(mod1)(mnmnm) 1),)(gcd(mod)(modmnmnnmkk)11 ()(ipnn歐拉函數歐拉函數int phi(int n)int ret = n,i;for(i = 2;i

3、 1) ret = ret * (n - 1) / n;return ret;復雜度O(logn)同余同余 (a+b)%n=(a%n+b%n)%n a*b%n=(a%n)*(b%n)%n快速冪快速冪 int pow(int a,int n,int p) if(!n) return 1;int t = pow(a,n 1,p);t = t * t % p;if(n & 1) t = t * a % p;return t 復雜度O(logn)，有非遞歸寫法，適用于高精度2222)(nnnnaaa同余方程同余方程)(modnbax )(modnbax)(modncmbax同余方程同余方程 求關于 x

4、 同余方程 ax 1 (mod b)的最小正整數解。 ax 1 (mod b) ax-1 0 (mod b) b|(ax-1) ax-1=kb ax-kb=1同余方程同余方程 由定理可知，ax+by=c有解當且僅當c|gcd(a,b) 對于不定方程，已知一組解，設為（x0,y0) 則通解為： x=x0+kb y=y0-ka 所以最終的最小整數解為 (x%b+b)%b 。歐幾里德擴展定理歐幾里德擴展定理 對于不完全為0的非負整數a,b那么存在唯一的整數x,y使得gcd(a,b)=ax+by。typedef long long ll;void exgcd(ll a,ll b,ll &x,ll &y) if(!b) x = 1; y = 0; else gcd(b,a % b,y,x); y -= x * (a / b); 剩余系剩余系 a(an)的1n次冪模n的值稱為a在模n下的剩余系，即 如果 則稱A