题解

16 条题解

  • 0
    @ 2009-11-05 18:48:48

    贪心都能贪80,真恶心……

  • 0
    @ 2009-11-03 21:54:16

    反质数的搜法即可。

  • 0
    @ 2009-11-10 16:34:30

    因为一个数可以分解成多个质数的乘积,

    若m:=a1^b1*a2^b2*a3^b3*...*an^bn

    那么m的约数个数为(b1+1)*(b2+1)*...*(bn+1)

    题目中说因子个数为n,所以就分解n了,把n分解成连乘的形式,

    然后计算m即可。

    优化

    1.将n分解成一列数,且它们是递减的,但不一定是单调的。

    2.将多个结果比较时,由于m过大,所以比较ln(m),即可

  • 0
    @ 2009-11-01 20:01:28

    先整理出1~130的素数放入数组A

    依次搜索A1..A2..A3...上的指数

    搜索时保证Ai上的指数

  • 0
    @ 2009-11-01 14:38:59

    感谢zhh1993的提示,我用搜索AC了

  • 0
    @ 2009-11-01 13:03:03

    Accepted 有效得分:100 有效耗时:0ms

    数据好弱,贪心能对7个点(我无语中………………)

    其实这题对于我来说最难的是怎么比较 x1^y1*x2^y2*x3^y3... 的大小,因为我还没学什么对数 - -!

    另外这题好像没什么必要分解质因数了…………可能是数据比较水吧

  • 0
    @ 2009-10-31 21:59:18

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 1150ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:1150ms

    这题数据加强了好多

    简单讲一下

    我是

    把n分解质因数 然后枚举前几个质数分别乘了什么数

    因为乘的数极大 因此就比较lx1^y1*x2^y2*x3^y3... 就是比较

    y1ln(x1)+y2 ln(x2)+y3 ln(x3)...就可以了

  • -1
    @ 2009-10-31 21:14:00

    Accepted 有效得分:100 有效耗时:0ms

    伤心啊T^T,听说重题了,先去好不容易做出来了比较简单的P1310,然后马上把程序拿来做这题,发现极限数据要17秒……再仔细一看,原来是找约数时10^9浪费太多时间了……改了改之后1秒出……高兴地直接交……90,发现一个字符错了……改了再交,还是90……数组0没开(关键是刚改了找约数的方法)……改了之后,终于过了……

    我好多废话啊……言归正传,我的方法是:先找n的约数,因为这种题目很容易发现所求的数m=2^a1+3^a2+.....pp(第p个素数)^ap,则n=(a1+1)*(a2+1)*.....*(ap+1),所以方法是先在程序开头打一个130以内的素数表~然后找k的约数,记录在数组中,开始搜索dfs(L,now,x,y).其中L表示上次搜索是搜k的第L个约数,now表示现在还剩的值,x表示再找ax(前面有说),y表示都目前为止算出的总值(但是这里y会很大,所以我们可以根据对数的性质将其用ln转化来代替!)。每次在now=1是判断更新(利用y来判断,因为要求满足的y最小,此处更新当前最小解和a)。最后就找到了a数组(其中的值都加了1,记得减1),输出即可

    中间当然还要一点剪枝,像最优解判断啦,但我认为关键在于L,大家可以自己在想想。另外还有这题的找约数当然如一开始说的不能用最裸的方法,否则……

    发现我挺有耐心的……

  • -1
    @ 2009-10-31 16:46:38

    什么是沙发啊????

    什么是沙发啊????

    什么是沙发啊????

    什么是沙发啊????

    什么是沙发啊????

    什么是沙发啊????

  • -1
    @ 2009-10-31 14:52:54

    hoho!!!

  • -1
    @ 2009-10-31 14:19:31

    not sofa

  • -1
    @ 2009-10-31 13:51:25

    占楼

  • -1
    @ 2009-11-10 12:34:01

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    测试完毕,通过!

    我- -其实..是用dp做的......没人用吗......。。

  • -1
    @ 2009-10-31 13:26:58

    沙发战争好河蟹 = =

  • -1
    @ 2009-10-31 13:10:16

    55555

  • -1
    @ 2009-10-31 12:27:47

    啊啊

    又被抢了..

  • 1

信息

ID
1685
难度
7
分类
动态规划 | 数论 点击显示
标签
递交数
207
已通过
34
通过率
16%
被复制
3
上传者