《noip中的数论数值.ppt》由会员分享，可在线阅读，更多相关《noip中的数论数值.ppt（14页珍藏版）》请在三一办公上搜索。
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(a,b),最大公约数与最小公倍数,int
2、 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)ret=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 return t复杂度O
3、(logn)，有非递归写法，适用于高精度,同余方程,同余方程,求关于 x 同余方程 ax 1(mod b)的最小正整数解。ax 1(mod b)ax-1 0(mod b)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。typedef long long ll;void exgcd(ll a,ll b,ll,剩余系,a(an)的1n次幂模n的值称为a在模n下的剩余系，即如果 则称A为完全剩余系，否则称A为不完全剩余系或者缩系。对于n，能得到完全剩余系的a的个数为,
