シーケンスを合計する方法は？

Question

は、どのように私は、次の手順を合計することができます

#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; 
} 

あなたはこれよりもよりよい解決策を知っていますか：

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

これは単純にC++でのO（n）のソリューションですか？私はO（1）またはO（log（n））を意味します。ありがとうございました:)と解決策

編集： ありがとうございました。誰かが溶液Oを希望する場合（SQRT（N））： パイソン：

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++：大nについて

#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)です。

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

注意：下記式

は、以下O(sqrt(n))擬似コードを与える（source）

を使用して（つまり、Pythonの有効であることを起こります） ：

Pythonで

• //オペレータが切り捨てされる整数分割です。
• math.sqrt()は、例示として使用されます。厳密に言えば、浮動小数点数の代わりにexact integer square root algorithmを使用する必要があります。

Answer 2

、式を使用：

（は超越番号です。）

詳細については、Euler-Mascheroni constantの記事を参照してください。 Divisor summatory function上のWikipediaの記事、

から撮影

Answer 3

。それは時間解決策を提供するはずです。

EDIT：整数平方根問題は、平方根または対数時間でも解くことができます。明らかでない場合もあります。

Answer 4

数字{1, 2, 3, ..., n}をsqrt(n)以下とsqrt(n)より大きいか等しい2つのグループに分けましょう。最初のグループでは、単純な繰り返しで合計を計算できます。第2のグループについては、以下のような観察を用いることができる。a > sqrt(n)の場合、n/a < sqrt(n)。そのため、[n/i] = d（1からsqrt(n)まで）の値を繰り返し、iという数字を[n/i] = dとして計算するのはこのためです。 O(1)にはdと固定されており、[n/i] = dはi * d <= n and i * (d + 1) > nを意味し、[n/(d + 1)] < i <= [n/d]となっています。

O(sqrt(n))で処理され、合計でO(sqrt(n))となります。

Answer 5

博学プロジェクトは、（N ^（1/3 + O（1）））時間Oにこの関数を計算するためのアルゴリズムをスケッチ、ページ8-9のセクション2.1を参照してください。

http://arxiv.org/abs/1009.3956

アルゴリズムは、間隔が最も近い整数に丸めたときに推定が正確になることを十分に薄くなるように選択される場合、十分に薄い間隔に領域をスライスし、がそれぞれに値を推定することを含みます。だから、ある範囲まで直接（100n ^（1/3）を提案しますが、これをいくつかの注意を払って修正することができます）、残りの部分をこれらの薄いスライスで行います。

は、このシーケンスの詳細についてはthe OEIS entryを参照してください。

編集：私は今Kerrek SBはコメントでこのアルゴリズムを言及していることがわかります。しかし、公正では、私は5年前にOEISにコメントを追加したので、私は彼の答えを投稿するのが悪いと感じません。 :)

答えはn log n付近であり、したがってでも書けるから、O（1）アルゴリズムは使用できないことにも言及する必要があります。は時間がかかります> log n。