浅尝辄止

[编程题]浅尝辄止

热度指数：466 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个正整数n，求 $\sum_{i=1}^{n}{\left[ \frac{n}{i} \right]}$ 。式子中[x]为下取整。

答案可能会很大，输出答案对998244353取模后的值。

示例1

输入

输出

示例2

输入

输出

备注:

1<=n<=10^13

算法知识视频讲解

Java

牛客196305255号

 public int work (long n) {
        long sum=0;
        for(long i=1;i*i<=n;i++) {
        	if(n/i!=i)
        		sum+=n/i+i*(n/i-n/(i+1));
        	else
        		sum+=n/i;
        }
        return(int)(sum%998244353);
    }

发表于 2021-04-02 13:23:18 回复(0)

Python

牛客540732497号

class Solution:
    def work(self , n ):
        numSum = n
        left = 2
        rightR = n
        rightL = n // 2
        while left <= rightL:
            numSum = numSum + (n // left) + (left - 1) * (rightR - rightL)
            left += 1
            rightR = rightL
            rightL = n // left      
        if left - rightL == 1:
            numSum += rightL
        return numSum % 998244353

发表于 2020-08-07 14:09:02 回复(0)