集训队作业poi解题报告poi0103_第1页
集训队作业poi解题报告poi0103_第2页
集训队作业poi解题报告poi0103_第3页
全文预览已结束

下载本文档

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

文档简介

1、反素数解题广西柳铁一中一、问题描述找出不超过N 的最大的反素数 M。反素数 M 即在 1 到 N 中约数最多的整数。二、解题思路由于本题中N2*109，因此对 1 到N 中的每个整数，通过逐一计算约数的个数从而找出其中约数最多者是不可取的。不妨换一个角度思考，与其由原数求约数，还不如由约数构造原数，这与题目所要求的约数最多这一条件关系更密切。众所周知：任何大于 1 的自然数都可以表示成素数的乘积，若不计素因子的次序，则这样的表示方法是唯一的。对于某一大于 1 的整数 M，不妨表示为：由排列组合知识不难求出，M 的约数个数为：(t1+1)* (t2+1)*(t3+1)。到此己很容易想到用母函数求

2、解。定义组 A，Ai表示有 i 个约数且不大于N 的最大的整数，初始时可以设：三、算法实现在编程时我发现，计算时所需的素数 d 极少，取前 15 个素数进行计算已经足够了。Const d :array1.15 of Long所需的前 15 个素数= (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47);Var A :array1.2,1.2000 of long;开 2 个 2000 的数组是为了便于滚动；2000 为约数最大的数目，这己足够用了T : Long;辅助变量，当前约数的最大值C :Beginx := 2; y=1;数组A 的更新标记for I :=

3、 1 to 15 do C := False;x := 3-x; y := 3-y;ax := ay; j := 1; k :=1;repeatj := j*dI;inc(k); tt：T；for L := T+1 downto 2 doif(ay中有约数个数为 L 的数)and (j*ay,L N )and (尚无含 k*L 个约数的数) or (当前ax,k*Lj*ay,L) then beginC := True;ax,k*L := j*ay,L;if k*Ltt then tt := k*L; end;tt := T;until j*dIN;if not C Then Break;End.三、算法性能分析1、 空间复杂度：4000 个Long。2、 时间复杂度：由于枚举的素数最多只有 15 个，而每个素数 d 在约数中出现的次数最多为 logdN。所以时间复杂度最多为：四、启发和总结1、本题要求反素数，题中给出的反素数定义本身就提供了求解的法：算出每个数的约数的个数。这很容易让人在这个不可能实现的方法上苦苦思索，而不能站在更高的角度通观问题。2、本题最重要的无非两个概念：数 N(N2*109)、N 的约数。前

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论