| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1258 人关注过本帖
标题:一道算法难题,求高手支招(不会降复杂度,电脑跑不起)
只看楼主 加入收藏
da浪淘沙
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2014-7-7
结帖率:0
收藏
已结贴  问题点数:10 回复次数:6 
一道算法难题,求高手支招(不会降复杂度,电脑跑不起)
令P(m,n)为m ×n乘法表中相异的数字个数。

例如,一个3 ×4乘法表如下所示

 × 1  2  3  4
 1  1  2  3  4
 2  2  4  6  8
 3  3  6  9  12

它有8个相异数字{1,2,3,4,6,8,9,12},故P(3,4) = 8。

已知:
P(64,64) = 1263、
P(12,345) = 1998以及
P(32,10^15) = 13826382602124302。

请求出P(64,10^16)。
2014-07-07 11:07
vvvcuu
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:12
帖 子:353
专家分:1253
注 册:2014-4-22
收藏
得分:5 
楼主,10的16次方也就是一亿个亿,目前限于个人水平,尚不知道该如何存储这么大的数字及其参与的运算。
不过,你的问题讨论的只是算法,而这算法不过是减法题而已。对于P(int x,  int y),假设x<y,只需要找出位于y和x*y之间的素数及其倍数的个数即可,然后用x*y减去这个数字即为答案。
算法很简单,实现也简单,只是存储是个问题。
手机回复的,不知道怎么打方幂次数。

代码测试环境:  WinXP+C-Free5.0.
2014-07-09 10:32
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:5 
大数运算

DO IT YOURSELF !
2014-07-09 10:48
da浪淘沙
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2014-7-7
收藏
得分:0 
2L,我们是要找好算法解决它,不是随便个算法就行了。有人解决这个问题,只需1秒,可惜我不认识他。
2014-07-09 12:48
da浪淘沙
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2014-7-7
收藏
得分:0 
暴力办法在这里是行不通的,即便你有那么大的存储,按计算机普通配置的主频,暴力跑可能花上一两年的时间,那时不现实的
2014-07-09 12:51
vvvcuu
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:12
帖 子:353
专家分:1253
注 册:2014-4-22
收藏
得分:0 
回复 4 楼 da 浪淘沙
认识那多人干什么,只要能学到他脑袋里的知识就行了。

在我看来, 如果没有现成的素数表,或者是有相当高深的数学功底,这个问题还真不容易做出来。因为这个问题本身就是纯数学问题。所谓高深的数学功底是指至少对矩阵,数论方面很有研究。

不同的人对于问题的考虑角度是不同的,这受限于个人的知识,生长生存环境。所以我才想出那样的算法。

如果他能在1秒内算出来这题的话,要么他知识水平很高,要么他家计算机很牛,比如在天河二号上跑。

如果可能的话,希望楼主把他算法贴上来。望不吝赐教。

[ 本帖最后由 vvvcuu 于 2014-7-10 09:25 编辑 ]

代码测试环境:  WinXP+C-Free5.0.
2014-07-10 09:23
woshiaokeman
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:60
专家分:123
注 册:2011-4-5
收藏
得分:0 
同意二楼,我第一反应也就是素数。。。
2014-08-24 20:34
快速回复:一道算法难题,求高手支招(不会降复杂度,电脑跑不起)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.029138 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved