网站大量收购闲置独家精品文档,联系QQ:2885784924

提高班第四讲初等数论.ppt

  1. 1、本文档共42页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
提高班第四讲初等数论

目录 1、素数 2、快速幂取模 3、唯一质因子分解定理 3、最大公约数(欧几里得算法) 4、扩展欧几里得算法 5、同余以及线性同余方程 6、特殊的线性同余方程组:中国剩余定理 素数 1、判断n是否为素数 Eratosthenes筛法 2)给定一个范围(求这个范围内的素数),进行如下步骤: 0.从2开始,2是第一个素数。也是第一个新素数。取出2。 1.筛掉所有新素数的倍数。 2.留下来的数里面第一个(最小的)是新素数。取出这个新素数。 3.重复1和2直到没有数存在。 memset(flag,0,sizeof(flag)); for(int i=2;i*i=1000000;i++) if(!flag[i]) { for(int g =i;g=1000000;g+=i) flag[g]=1; } 快速幂取模 1.模取运算的性质 (1)(a+b)%c = ((a%c)+(b%c))%c (2)(a*b)%c = ((a%c)*b)%c 快速幂(风格简洁) __int64 quickmod(__int64 x, __int64 n) { __int64 pw = 1; while (n 0) { if (n 1) // n 1 等价于 (n % 2) == 1 pw *= x; x *= x; n = 1; // n = 1 等价于 n /= 2 } return pw; } 质因子分解定理 唯一因子分解 唯一质因子分解定理:合数a仅能以一种方式,写成如下的乘积形式: a=p1e1p2e2…prer 其中pi为素数,p1p2…pr,且ei为正整数。 那么怎么求的一个合数n的所有素因子呢? 暴力法: 1、先求出每一个n的素因子,然后穷举 for(int i=2;i*i=n;) { if(n%i==0) { couti ; while(n%i==0) { n/=i; } } else i++; } if(n!=1) coutnendl; 初等数论的概念 最大公约数 gcd(最大公因子) LCM(Least Common Multiple) 扩展欧几里得 算法 扩展欧几里得典型例题: 同余 同余的性质 例:求3406写成十进位数时的个位数. 模的逆元 求解模线性方程 定理:方程ax=b(mod n)对于未知量x有解,当且仅当gcd(a, n)|b 定理:方程ax=b(mod n)或者对模n有d个不同的解,其中d=gcd(a, n)或者无解。 求解模线性方程 定理:假设方程ax=b(mod n)有解(即有d|b,其中d=gcd(a, n)),x0是该方程的任意一个解,则该方程对模n恰有d个不同的解,分别为:xi=x0+i(n/d)(i = 1, 2, …, d-1)。 求解模线性方程 定理:设d=gcd(a, n),假定对整数x’和y’,有d=ax’+ny’。如果d|b,则方程ax=b(modn)有一个解的值为x0,满足x0=x’(b/d)mod n。 (中国剩余定理CRT)设m1,m2,...,mk是两两互素的正整数,即gcd(mi,mj) =1,i≠j,i,j = 1,2,...,k    则同余方程组:    x≡b1 (mod m1)    x≡b2 (mod m2)    ...    x≡bk (mod mk)    模[m1,m2,...,mk]有唯一解,即在[m1,m2,...,mk]的意义下,存在唯一的x,满足:    x≡bi mod [m1,m2,...,mk],i = 1,2,...,k 本周上机时间: 变更为星期六下午2点!! 上机小tips: 1、学会跟榜单(网上邻居有) 2、英文题有时候其实很水的~~ 3、边界条件考虑清楚 4、基础班题目提高班可做,提高班题目基础班可酌情做~~~ 5、时间复杂度 6、上完机总结很重要(推荐写博客) ZZY博客某页 推荐书本: GCD递归定理:对任意非负整数a和任意正整数b,gcd(a, b) = gcd(b, a mod b)。 Evaluation only. Created with Aspose.Slides for .N

文档评论(0)

shaoye348 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档