> 题目归结为判断两个自然数多集（允许有重复元素的集合）a, b是否相等。用快排比较的效率是O(nlgn)，下面提出一种O(n)的方法供大家参考。
> 
> 猜想：若 sum(a^i) = sum(b^i)，i = 0, 1, 2, 则 a = b。
> 证明：？
> 
> 注意
> sum(s^0) 是多集s中元素的数目
> sum(s^1) 是多集s中元素的和
> sum(s^2) 是多集s中元素的平方和
> 
> 即比较多集的三个统计值即可。以上算法是AC的。但是我还没有一个满意的证明。

可以参考的思路：
a1^2 + b1^2 = a2^2 + b2^2
推出
a1 = a2, b1 = b2

• Re:一种O(n)算法 (119) darkcaller 2010-12-12 12:44:20