导致o（n2）到了1000多ms 而n2logn的 用g++竟然刷到421ms g++比c++快很多啊。
g++ 还是不错的阿

• 求gcd已经需要O(lgn)时间，你怎么O(n^2) (70) frkstyc 2006-03-27 14:16:16
  • 哦对了 我把gcd忽略了 (0) xiaxia 2006-03-27 14:19:55
  • gcd不是本质上的，可以用乘法代替判相等。 (0) achilles 2006-03-27 15:48:22
    • 但这个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