> 题目归结为判断两个自然数多集（允许有重复元素的集合）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的。但是我还没有一个满意的证明。
搜索了一下，一大堆反例，列举几个
3 3 6和2 5 5
3 3 9和1 7 7
3 4 8和2 6 7