【题解】天花板

题意

给你 $n$ ，求 $\sum_{i=1}^n\left \lceil \frac{n}{i} \right \rceil$ 的值是多少。

题解

$\left \lceil \frac{n}{i} \right \rceil$ 不像向下取整那样可以用整除分块去直接求下一个区间，那么我们怎么考虑呢。由于 $n$ 最大能到 $10^9$ ，可以明确 $\left \lceil \frac{n}{i} \right \rceil$ 不同的值只有 $\sqrt{n}$ 级别个，所以 $\left \lceil \frac{n}{i} \right \rceil$ 中的 $i$ 在某一个区间之内，向上取整的值都是一下的，那么我们怎么去确定右区间呢。实际上我们可以用二分来确定右区间。二分的左右边界，若当前要除的值为 $i$ ，那么左边界就是 $i$ ，右边界为 $n$ ，若 $\left \lceil \frac{n}{mid} \right \rceil\ <\left \lceil \frac{n}{i} \right \rceil$ ，说明右边界大了即 $r=mid-1$ ，否则 $l=mid+1$ 。找了向上取整的右边界，我们就可以快速的求和了。

复杂度

时间复杂度为 $O(\sqrt{n}log(n))$
空间复杂度为 $O(1)$

代码

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return long长整型
     */
    int Find(int n,int i)
    {
        int x=ceil(1.0*n/i);
        int l=i;
        int r=n;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(ceil(1.0*n/mid)<x)
                r=mid-1;
            else
                l=mid+1;
        }
        return r;
    }
    long long Sum(int n) {
        // write code here
        long long ans=0;
        for(int i=1,last; i<=n; i=last+1)
        {
            last=Find(n,i);
            ans+=(last-i+1)*int(ceil(1.0*n/i));
        }
        return ans;
    }
};