厦大OJ 1051
by Charlie on Aug.05, 2008, under ACM Life, Hits 1183
原文见
:ACM, xmu
原题http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1051
题目大意：输入一个数N，求出N的组合，用它的公因数的次方表示出来。例如输入为5，起组合为5*4*3*2*1，输出应为2^3*3*5。这题主要难点在于N的取值最大可为1000000。而时间只有1s。
对于这题，我的想法是对于每一个数都分解成它的因数的乘积形式，并将每个因数的个数记录起来。由上可知，N的取值能到1000000，而对于每个数的因数的求解也将耗费大量时间，明显，1s必然不够我们花销。
于是，我便做了些优化。如对a运算时，假如a%2==0，则，我们便将a / 2标记，这样就可以不用处理a / 2。分析可知，它的截掉一半的枝，效果相当可观了。
另外还有些优化，在对每个数的因数求解方面，都是些常用的优化，不多作解释。
现在的问题是超时，测过，跑完1000000需要3.43s。暂时未有更好优化，希望大家能说说大家的想法。。。
题目大意：输入一个数N，求出N的组合，用它的公因数的次方表示出来。例如输入为5，起组合为5*4*3*2*1，输出应为2^3*3*5。这题主要难点在于N的取值最大可为1000000。而时间只有1s。
对于这题，我的想法是对于每一个数都分解成它的因数的乘积形式，并将每个因数的个数记录起来。由上可知，N的取值能到1000000，而对于每个数的因数的求解也将耗费大量时间，明显，1s必然不够我们花销。
于是，我便做了些优化。如对a运算时，假如a%2==0，则，我们便将a / 2标记，这样就可以不用处理a / 2。分析可知，它的截掉一半的枝，效果相当可观了。
另外还有些优化，在对每个数的因数求解方面，都是些常用的优化，不多作解释。
现在的问题是超时，测过，跑完1000000需要3.43s。暂时未有更好优化，希望大家能说说大家的想法。。。
1 Comment for this entry
Leave a Reply
-
Welcome to 5ushare!
Thanks for dropping by! Feel free to join the discussion by leaving comments, and stay updated by subscribing to the RSS feed. See ya around!
Anything,contact me.Here is My Chinese Blog
February 15th, 2009 on 6:04 pm
http://www.5ushare.com - cooooolest domain name)))
————————
internet signature: http://dewat.ru/
[Reply]