noip中的数论数值问题_第1页
noip中的数论数值问题_第2页
noip中的数论数值问题_第3页
noip中的数论数值问题_第4页
noip中的数论数值问题_第5页
已阅读5页，还剩9页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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)最大公约数与最小公倍数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)%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|(ax-1)<=>ax-1=kb<=>ax-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;}else{gcd(b,a%b,y,x);y-=x*(a/b);}}剩余系a(a<n)的1~n次幂模n的值称为a在模n下的剩余系，即如

人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论