@pinkex
2018-08-20T11:07:56.000000Z
字数 1128
阅读 521
设最终所求的是,。如果一个小于等于,则将存在中;否则存在中。时间复杂度(操作一次):空间复杂度:正确性证明:主要是证明大于的两个数不会在数组里占用相同的位置。由我们得到的式子(就是莫比乌斯反演推出的式子),所有被计算的数都是形如的数。现假设有两个不同的数,和(),假设。那么显然有。由于和均是小于的,我们只需要证明就能说明假设不成立了,也就是正确性证完了。由于这个东西是有单调性的,我们只要证明就行了。假设,,则设其为。则有:,,两式相减得到由于其实是,必有,则。所以假设不成立。原命题得证。