c++ - 如何求和序列？

Question

我如何总结以下序列:

⌊n/1⌋ + ⌊n/2⌋ + ⌊n/3⌋ + ... + ⌊n/n⌋

这只是 C++ 上的 O(n) 解决方案:

#include <iostream>
int main()
{
   int n;
   std::cin>>n;
   unsigned long long res=0;
   for (int i=1;i<=n;i++)
   {
      res+= n/i;
   }
   std::cout<<res<<std::endl;
   return 0;
}

你知道比这更好的解决方案吗？我的意思是 O(1) 或 O(log(n))。感谢您的宝贵时间:) 和解决方案

编辑: 感谢您的所有回答。如果有人想要解决方案 O(sqrt(n)): python :

import math
def seq_sum(n):
 sqrtn = int(math.sqrt(n))
 return sum(n // k for k in range(1, sqrtn + 1)) * 2 - sqrtn ** 2
n = int(input())
print(seq_sum(n))

C++:

#include <iostream>
#include <cmath>
int main()
{
   int n;
   std::cin>>n;
   int sqrtn = (int)(std::sqrt(n));
   long long res2 = 0;
   for (int i=1;i<=sqrtn;i++)
   {
      res2 +=2*(n/i);
   }
   res2 -= sqrtn*sqrtn;
   std::cout<<res2<<std::endl;
   return 0;
}

Answer 1

这是Dirichlet's divisor summatory function D(x) .使用以下公式 (source)

在哪里

给出以下 O(sqrt(n)) 伪代码(恰好是有效的 Python):

def seq_sum(n):
  sqrtn = int(math.sqrt(n))
  return sum(n // k for k in range(1, sqrtn + 1)) * 2 - sqrtn ** 2

注意事项:

• Python中的//操作符是整数，即截断、除法。
• math.sqrt() 用作说明。严格来说，这应该使用 exact integer square root algorithm而不是 float 学。