题解 | #浅尝辄止#

题目：给定一个正整数n，求
​式子中[x]为下取整。
答案可能会很大，输出答案对998244353取模后的值。
方法一：暴力解法
直接暴力求解i从1到n时的累加和

public class Solution {
    /**
     * 
     * @param n long长整型 
     * @return int整型
     */
    int mod=998244353;
    public int work (long n) {
        // write code here
        if(n==1)return 1;
        long res=0;
        for(int i=1;i<=n;i++){
            res+=n/i;
        }
        res%=mod;
        return (int)res;
    }
}

复杂度：
时间复杂度：,i从1取到n，时间复杂度过大，会超时
空间复杂度：,额外变量的空间复杂度为常数级
方法二：数论分块

对于一类含有⌊⌋的求和式 (n 为常数)，由于⌊⌋单调不增，故存在多个区间[l,r], 使得⌊⌋=⌊⌋(i,j∈[l,r]) 成立。对于任意一个i，最大的满足上式的
证明如下：

对于每一个, 存在区间 ,
使得，
区间 贡献即为。

import java.util.*;


public class Solution {
    /**
     * 
     * @param n long长整型 
     * @return int整型
     */
    int mod=998244353;
    public int work (long n) {
        // write code here
        long res=0;
        for(long l=1,r=0;l<=n;l=r+1){//l指针需要移动到r指针的下一位
            r=n/(n/l);
            res+=(r-l+1)*(n/l);
            res%=mod;
        }
        return (int)res;
    }
}

复杂度：

时间复杂度：,
空间复杂度：,额外变量的空间复杂度为常数级