集训队作业number解题报告_第1页
全文预览已结束

付费下载

下载本文档

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

文档简介

SecretNumber问题描次：S：我也知道了已知x,y，求所有满足上述的数对(a,b)，其中(2≤x≤a<b≤y≤550)符号约集合M(a,b)：M(a,b)={(x,y):ab=xy,1<x<y}。S(a,b)：S(a,b)={(x,y):a+b=x+y,1<x<y}问题分f(1,a,b)(M(a,b)S：我也不知道a,b，且我知道你不知道。a,这说明|S(a,b)|>1。否则|S(a,b)|=1S先生就能够确定(a,b)S(a,f(1,u,v)不成立，说明S先生无法确定M先生不知道。f(2,a,b)((S(a,b)1)((x,y):(x,y)S(a,b)f(1,x,y))f(1,a,M：我知道了M(ab)f(2xy)的数对(xy)(ab)M先生无法确定(a,b)。因此，有f(3,a,b)(({(x,y):((x,y)M(a,b))f(2,x,y)}{(a,b)})f(2,a,SS(a,b)f(3xy)的数对(xy)(ab)S先生无法确定(a,b)。因此，有f(4,a,b)(({(x,y):((x,y)S(a,b))f(3,x,y)}{(a,b)})f(3,a,f(1,a,b)M(a,b)f(2,a,b)(S(a,b)1)((x,y):(x,y)S(a,b)f(1,x,f(3,a,b){(x,y):((x,y)M(a,b))f(2,x,y)}{(a,f(4,a,b){(x,y):((x,y)S(a,b))f(3,x,y)}{(a,函数f(4,a,b)便可以判断数对(a,b)是否满足的要求算法优为了降低算法时间复杂度，考虑化简f(2,a,b)的求法。在这之前，需要假定：在给定范围内，一个充分大的偶数（7大，可以分解为两个不同的奇质数的和。下面分情况f(2,a,b)所需要满足的条件。这时|S(a,b)|>1，故f(2,a,b)成立，当且仅当(xyxyS(abf(1,xya+b即|M(x,y)|=1，这就是说f(1,x,y)不成立，故f(2,a,b)不成立。a+b{(x,y):xyab,2xy,xmod2{(x,y):xyab,1xy,ymod2{(2,ab容易证明，前两类中的数对(x,y)f(1,x,y)f(2,a,b)成立，f(1,2,a+b-2)a+b-2是质数，则|M(2,a+b-2)|=1f(1,2,a+b-2)综上所述，f(2,a,b)成立，当且仅当数对(a,b)a+ba+

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

温馨提示

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

最新文档

评论

0/150

提交评论