题意：

给你一个数字 ，求 。

解法一（暴力求解，不可AC）：

直接循环 按题意计算过去即可。
代码：

class Solution {
public:
    const int mod=998244353;
    int work(long long n) {
        int ans=0;
        for(long long i=1;i<=n;i++){//注意开 long long
            ans=(ans+n/i)%mod;
        }
        return ans;
    }
};

时间复杂度： ，程序中有一个 的循环，故时间复杂度为
空间复杂度： ，程序中没有使用额外的数组，也没有递归调用的过程，只有有限个变量，故空间复杂度为

解法二（数论分块）：

我们首先介绍一下数论分块。
数论分块一般用来计算如下形式的值

而本题求解的问题就是数论分块的基本形式。
对于任意的 ，存在一个区间 使得区间内的 值都相等。
例如， 时：

引理：

对于任意一个 ，满足上述的 。

证明：

对于满足 有：

则：


故：

故 的最大值为
具体的，对于每一个区间的左端点 ，我们可以求出当前区间的右端点 ，然后我们程序就可以分区间进行计算了。
代码：

class Solution {
public:
    const int mod=998244353;
    int work(long long n) {
        int ans=0;
        //i为左端点，j为右端点，每次计算完后跳到下一个区间，即i=j+1
        for(long long i=1,j=0;i<=n;i=j+1){
            j=n/(n/i);//计算右端点
            ans+=1ll*(j-i+1)*(n/i)%mod;
            ans%=mod;
        }
        return ans;
    }
};

时间复杂度：
关于数论分块，我们以下给出时间复杂度的证明
我们可以考虑有多少个不同的

1. 当时，最坏情况每个 都不相同，最多只有 个不同的
2. 当 时，显然 ，故最多只有 个不同的
   综上所述，我们最多只有 个不同的 ，而相同的 一定在连续的一段区间内，我们可以 计算这段区间的答案，故总的时间复杂度为

空间复杂度： ，程序中没有使用额外的数组，也没有递归调用的过程，只有有限个变量，故空间复杂度为