浅尝辄止题解

【前言】
非常简单的数学题。

【暴力】
直接模拟即可，复杂度O(n)

【正解】
有很多项是完全相同且连续的，因此可以采用计算这一项出现了多少次来简化计算。
我们采用这样的做法，枚举1到x，计算以这个数作为答案被记录了多少次，这时我们就快速计算了很大一段的和，我们假设已经计算了y到n这几项的和，对于剩下的1到y-1，暴力。
可知y=[n/(x+1)]+1
我们来看复杂度，是O(x+n/(x+1))的，可以近似为O(x+n/x)，根据基本不等式，x取 时达到最小。
所以最后复杂度为O( ).

参考代码：

class Solution {
public:
    /**
     * 
     * @param n long长整型 
     * @return int整型
     */
    int work(long long n) {
        // write code here
        int ans=0;
        long long l=n;
        for (long long i=2;1ll*i*i<=n;i++) 
        {
            long long x=l-(n/i);
            ans=(ans+((i-1)*x%998244353))%998244353;
            l=n/i;
        }
        for (long long i=1;i<=l;i++) ans=(ans+(n/i)%998244353)%998244353;
        return ans;
    }
};