noip中的数论数值

《noip中的数论数值》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、noip中的数论/数值有关数学的函数C/C++中有关数学的函数在math.h中。使用时需要注意精度问题。math.h中有个叫y0的函数，会与全局变量名冲突。log()是数学中的ln，log10()是数学中的lg，没有logab的函数，需要用换底公式。三角函数、对数函数等很慢。尽量避免除法。double有误差，pow(10,100)-(pow(10,100)+1)=0！二项式定理与杨辉三角最大公约数与最小公倍数最大公约数gcd(a,b)，也记为(a,b)最小公倍数lcm(a,b)gcd(a,b)=gcd(b,a%b)lcm(a,b)=ab/gcd

2、(a,b)最大公约数与最小公倍数intgcd(inta,intb){intr;while(b){r=a%b;a=b;b=r;}returna;}欧拉函数小于n且与n互质的数的个数称为欧拉函数。若n为素数则欧拉函数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)

3、%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)的最小正整数解。ax≡1(modb)<=>ax-1≡0(modb)<=>b

4、(ax-1)<=>ax-1=kb<=>ax-kb=1同余方程由定理可知，ax+by=c有解当且仅当c

5、gcd(a,b)对于不定方程，已知一组解，设为（x0,y0)则通解为：x=x0+kby=

6、y0-ka所以最终的最小整数解为(x%b+b)%b。欧几里德扩展定理对于不完全为0的非负整数a,b那么存在唯一的整数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