16 条题解
-
0
wsdhhh LV 8 @ 2009-11-05 18:48:48
贪心都能贪80,真恶心……
-
0
一路向东 (柔情使者) LV 9 @ 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
M36_slugger LV 10 @ 2009-11-01 13:03:03
Accepted 有效得分：100 有效耗时：0ms
数据好弱，贪心能对7个点(我无语中………………)
其实这题对于我来说最难的是怎么比较 x1^y1*x2^y2*x3^y3... 的大小，因为我还没学什么对数 - -！另外这题好像没什么必要分解质因数了…………可能是数据比较水吧
-
0
编译通过...
├ 测试数据 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
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
db_db_Jacky LV 10 @ 2009-10-31 13:51:25
占楼
-
-1
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
测试完毕,通过!
我- -其实..是用dp做的......没人用吗......。。 -
-1
rmzxa55435 LV 8 @ 2009-10-31 13:26:58
沙发战争好河蟹 = =
-
-1
honghaijie LV 9 @ 2009-10-31 12:27:47
啊啊
又被抢了..
wsdhhh
LV 8
@ 2009-11-05 18:48:48
- 1