论坛 › 编程擂台 › 数字乘积

无心人 发表于 2009-2-26 13:36:20

怀疑复合条件的数字的因子只能是2，3

mathe 发表于 2009-2-26 14:09:58

P(2678789) = 8
这个数马上就产生一个含因子7的数。
你没有分析数字1，当然还有5也不能完全省略，比如数字395也是可以的，3*9*5=135,1*3*5=15,1*5=5

无心人 发表于 2009-2-26 14:13:19

395你给我逆推到6？？
呵呵

无心人 发表于 2009-2-26 14:13:59

现在，我想，逆推出的数字如果不是题目求的素数必定是2的倍数

无心人 发表于 2009-2-26 14:14:53

我说的那些是找最小的原则

你说的是全部啊

无心人 发表于 2009-3-1 12:13:48

想穷举出所有的P(n) = 9且n只有因子2，3，5，7的数字
打算Cache出1-10^8的n的P值和0-9999的数字乘积值

medie2005 发表于 2009-3-1 14:58:23

为什么没人愿意用逆推法来编程试一试呢?初始一个最大长度,用dfs应该不会很慢的.

medie2005 发表于 2009-3-2 13:19:19

穷举10^60内素因子只为2,3,5,7的数.然后,对某个n=2^a*3^b*5^c*7^d,计算n的十进制表示的数字的乘积s,然后n到s就有一条边.
通过这样的方法,我们可以得到一个图.
由于只有头部的数是素数,其余的数都是只含2,3,5,7素因子(尾部也可为0).
因此,如果得到的图中,有一条长为k的路径,那么,我们得到头部,然后再由头部得到其前驱,从中选取最小的素数,就得到一个局部的最优解.
若我们对图中所有长度为k的路径,都得到一个局部最优解,从中选优,我们就得到了一个近似最优解.
假定这个近似最优解有T位,我们接下来就是要证明这个近似解是最优或者找到最优解.
我们可以穷举10^T内素因子2,3,5,7的数,然后再用上面的方法就可以了.

无心人 发表于 2009-3-2 17:43:17

粗略估计在10^60内你说的数字就是
小于199 * 125 * 85 * 70个

不知道每个数字的对应数字是多少候选？？
应该是一对多啊

无心人 发表于 2009-3-2 17:44:32

有两点可以肯定
1、2，3必须同时存在
2、5的幂不能大于10

查看完整版本: 数字乘积