题目陈述

• 大意：求解表达式的值

算法一：朴素算法

算法思路

• 暴力算法，枚举每个，计算其对答案的贡献，遍历所有的即可

• 代码实现

  class Solution {
  public:
    int work(long long n) {
        long long ans = 0;
        for (int i = 1; i <= n ; i ++ ) //枚举所有的i
            ans += n / i; //计算i对答案的贡献
        ans %= 998244353; //对答案取模
        return ans;
    }
  };

  复杂度分析

• 时间复杂度，所有的都遍历了一遍，时间复杂度为
• 空间复杂度，定义了变量，为

算法二：整除分块

算法思路

• 首先，要了解整除分块是干什么的？整除分块就是解决本题的这种形式的问题，即

• 上面的括号代表向下取整，即整除
• 我们这道题的题目是最基本的形式
• 我们以为例子，如下图

• 我们将都换成具体的正整数

• 我们可以发现对于一个，往往是一段区间的整除值都是同一个值（废话）
• 此处我们感性理解一下，比如从除的结果是
• 或看为，除法带余数，就出现一段区间他们的商都是一个值
• 现在，假如我们通常知道了区间内的某一个下标（一般是左端点），如何求得跟它所在区间的右端点？
• 设，显然我们可以这样表示，而把设置为倍数，显然也就是的值
• 对于右端点,必然有
• 反证法，若则，可以令,
• 就得到了区间内比右端还靠右的满足条件的点
• 所以：对于右端点,必然有
• 我们就可以根据这个性质，通过，求得，再通过求得
• 故对于一个区间，我们知道左端点，即可以通过公式计算右端点，代码中写作r = n / (n / i)，注意此处为整除
• 既然我们知道了当前区间的左右端点，那么如何知道下一个区间的左端点呢？很显然，也就是右端点的下一个位置，即
• 于是我们只要这样这样遍历下去，就可以求得的值

代码实现

class Solution {
public:
    int work(long long n) {
        long long ans = 0;
        for (long long l = 1, r; l <= n; l = r + 1) //整除分块
        {
            r = n / (n / l); //获取右端点
            ans += (r - l + 1) * (n / l); //将当前区间的贡献加到答案上面
        }
        ans %= 998244353; //对答案进行取模
        return ans;
    }
};

复杂度分析

• 时间复杂度，为整除分块的时间复杂度，即，下面给出整除分块的时间复杂度证明：
• 对于，这样的最多有个，考虑映射关系，一个与一个映射（实际上可能多个对应一个），最多也有个
• 对于，有，这些都会落在这个区间上面，最多就个
• 总共最多个，即分块的个数最多为个每个分块表达式求值为，总得整除分块时间复杂度为级别，证毕
• 空间复杂度，定义了，为