Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

gcd不是本质上的，可以用乘法代替判相等。

Posted by achilles at 2006-03-27 15:48:22 on Problem 2780
In Reply To:求gcd已经需要O(lgn)时间，你怎么O(n^2) Posted by:frkstyc at 2006-03-27 14:16:16

Followed by:

但这个lgn的因子你怎么免掉？ (0) frkstyc 2006-03-27 15:49:19
- hash平均情况下是常数时间。这个logn是哪里来的？ (0) achilles 2006-03-27 16:08:40
  - 你的做法不是解题报告的做法了 (31) frkstyc 2006-03-27 16:23:06
    - 报告的做法明显分析错了复杂度。gcd的复杂度被忽略了。对于大量的运算来说，gcd很费时间的 (33) achilles 2006-03-27 16:43:34
      - 果然...按照1118的方法做，算个gcd就tle了 (0) qiqilrq 2007-11-12 07:53:44
怎么乘法判相等阿，斜率分子乘分母，但是怎么计数阿？ (0) xiaxia 2006-03-27 16:48:08
分母乘上一个大于N的数加上分母。不过这样似乎还是要gcd啊~？ (0) palmtenor 2006-03-27 18:04:58
- 拿分子除分母然后乘上一个数取整当hash code (0) frkstyc 2006-03-27 18:10:02

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator