关于 ABC 的一点困惑

refla · 发表于 2009-4-4 18:32:22

为什么 ABC 包的计算时间差别如此之大？在我的机器上，从 30 分钟到 12个半小时都有！

[ 本帖最后由 refla 于 2009-4-4 18:38 编辑 ]

fwjmath · 发表于 2009-4-4 20:10:22

在不同的区间内的ABC包长度不同，这是算法决定的~~~这涉及到一点数学问题~~~
如果这个搜索区间里边的数都比较smooth，也就是说没有大的质因子的话，那么搜索需要比较长的时间，因为组合情况比较多~~~
相反，如果这些数的质因子都不小的话，搜索用时就会短得多~~~

refla · 发表于 2009-4-5 17:37:13

refla · 发表于 2009-4-5 17:38:52

虽然没听懂（是因为自己水平低啦），但还是觉得你很厉害。。。。

fwjmath · 发表于 2009-4-5 18:06:45

那我换种说法~~~
ABC的算法是要把一个数拆成两个数的乘积的，一个数拆法越多，就需要越多的时间去枚举每种拆法，看能不能产生符合条件的ABC三元组。
有些数可以被很多数整除，比如说12能被1,2,3,4,6,12整除。这种数就要比较多的时间来拆。
有些数只能被几个数整除，比如说1067只能被1,11,97,1067整除，这种数就不需要这么多时间来拆。
那么，如果区间内第一种数比较多，那么当然计算时间就长；如果第二种数比较多，计算时间就比较短~~~

WiZarD811 · 发表于 2009-4-5 18:57:58

深入浅出,果然厉害…话说科学知识普及也是分布式计算的一大功能.

refla · 发表于 2009-4-6 06:59:42

彻底明白啦

refla · 发表于 2009-4-6 07:00:42

正是

fwjmath · 发表于 2009-4-6 18:46:45

呵呵~~~明白就好~~~证明我打的字还是有用的~~~

merlinl · 发表于 2009-4-6 22:27:22

提示: 作者被禁止或删除内容自动屏蔽

		自动登录	找回密码
密码			新注册用户

merlinl merlinl 当前离线积分 38355 UID 13474 在线时间小时最后登录 1970-1-1 头像被屏蔽	发表于 2009-4-6 22:27:22 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽
	[建议]上传图片前先进来了解下相关经验
	回复使用道具举报

关于 ABC 的一点困惑

回复 #1 refla 的帖子

评分

回复 #5 fwjmath 的帖子

回复 #6 wzd811 的帖子