题解 | #浅尝辄止#

思路：

题目的主要信息：

给定n，求 $\Sigma^n_{i=1}\lfloor n/i \rfloor$ ，输出答案对998244353取模后的值
$\lfloor \rfloor$ 运算表示向下取整

方法一：暴力法（超时）
具体做法：
遍历1到n，暴力累加答案并取模

class Solution {
public:
    int work(long long n) {
        long long res = 0;
        int mod = 998244353;
        for(long long i = 1; i <= n; i++){ //注意n为long long 
            res = (res + n / i) % mod; //按照公式累加
        }
        return (int)res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，一共遍历 $n$ 次
空间复杂度： $O(1)$ ，常数级变量

方法二：整除分块思路
具体做法：
对于整除我们可以发现如下的规律：
图片说明
因此我们可以对1到n分区间处理，区间内的整除值都是相同的，都等于 $n/left$ ，而区间我们如果令 $k=n/left$ ，就会发现这个区间右边界为 $n/k$ ，而这段区间的相加结果就是区间长度乘上区间值。

class Solution {
public:
    int work(long long n) {
        long long res = 0;
        int mod = 998244353;
        long long left = 1, right = n;
        while(left <= n){
            right = n / (n / left); //找到相同商数的区间右界
            res = (res + (right - left + 1) * (n / left)) % mod; //相同数*区间长度
            left = right + 1; //更新左界
        }
        return (int)res;
    }
};

复杂度分析：

时间复杂度： $O(\sqrt n)$ ，因为对于被除数 $n$ 最多有 $2\sqrt n$ 个不同的商，因为当 $i<=\sqrt n$ 时，一共最多有 $\sqrt n$ 个商，而这些商又可以作为除数对应当 $i>=\sqrt n$ 时的商
空间复杂度： $O(1)$ ，常数级变量