《noip中的数论数值.ppt》由会员分享，可在线阅读，更多相关《noip中的数论数值.ppt（14页珍藏版）》请在金锄头文库上搜索。
1、noipnoip中的数论中的数论中的数论中的数论/ /数值数值数值数值有关数学的函数有关数学的函数有关数学的函数有关数学的函数C/C+中有关数学的函数在math.h中。使用时需要注意精度问题。math.h中有个叫y0的函数，会与全局变量名冲突。log()是数学中的ln，log10()是数学中的lg，没有logab的函数，需要用换底公式。三角函数、对数函数等很慢。尽量避免除法。double有误差，pow(10,100)-(pow(10,100)+1)=0！二项式定理与杨辉三角二项式定理与杨辉三角二项式定理与杨辉三角二项式定理与杨辉三角最大公约数与最小公倍数最大公约数与最小公倍数最大公约数与最小公
2、倍数最大公约数与最小公倍数最大公约数gcd(a,b)，也记为(a,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为素数则欧拉函数欧拉函数欧拉函数欧拉函数int phi(int n)int ret = n,i;for(i = 2;i 1) re
3、t = ret * (n - 1) / n;return ret;复杂度O(logn)同余同余同余同余(a+b)%n=(a%n+b%n)%na*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)，有非递归写法，适用于高精度同余方程同余方程同余方程同余方程同余方程同余方程同余方程同余方程求关于x同余方程ax1(modb)的最小正整数解。ax1(modb)
4、ax-10(modb)b|(ax-1)ax-1=kbax-kb=1同余方程同余方程同余方程同余方程由定理可知，ax+by=c有解当且仅当c|gcd(a,b)对于不定方程，已知一组解，设为（x0,y0)则通解为：x=x0+kby=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;elsegcd(b,a%b,y,x);y-=x*(a/b);剩余系剩余系剩余系剩余系a(an)的1n次幂模n的值称为a在模n下的剩余系，即如果则称A为完全剩余系，否则称A为不完全剩余系或者缩系。对于n，能得到完全剩余系的a的个数为
