【牛客编程巅峰赛S1第4场】浅尝辄止

题目

给定一个正整数 $n$ ，求 $\sum_{i=1}^{n}{\left[ \frac{n}{i} \right]}$ 。式子中 $[x]$ 为下取整。
输出答案对 998244353 取模后的值。

解题思路

整除分块

以 10 为例：

$i$	1	2	3	4	5	6	7	8	9	10
$\lfloor n/i \rfloor$	10	5	3	2	2	1	1	1	1	1

表中同样的值会连续出现，可根据不同的数值划分出不同的分块。

假设已知某个分块的左端点 $left$ ，求出右端点 $right$ ，则有 $\lfloor \frac{n}{left} \rfloor = \lfloor \frac{n}{right} \rfloor$ 。
令 $k = \lfloor \frac{n}{left} \rfloor$ ，则 $right = \lfloor \frac{n}{k} \rfloor$ 。
范围 $[left, right]$ 内的数值都相等，即为 $k$ 。

C++代码

class Solution {
public:
    /**
     * 
     * @param n long长整型 
     * @return int整型
     */
    int work(long long n) {
        // write code here
        int mod = 998244353;
        long long ans = 0;
        long long left = 1;
        long long right;
        while(left <= n){
            long long k = n / left;
            right = n / k;
            ans += (right - left + 1) * k;
            ans %= mod;
            left = right + 1;
        }
        return (int)ans;
    }
};