Hướng dẫn sum of sequence c++ - tổng của chuỗi c ++

EDIT: Bài toán căn bậc hai cũng có thể được giải quyết ở căn bậc hai hoặc thậm chí thời gian logarit quá - chỉ trong trường hợp không rõ ràng.

Đã trả lời ngày 4 tháng 1 năm 2015 lúc 18:20Jan 4, 2015 at 18:20

AlecalecAlec

31.2K5 Huy hiệu vàng62 Huy hiệu bạc114 Huy hiệu đồng5 gold badges62 silver badges114 bronze badges

0

Dự án polymath phác thảo một thuật toán để tính toán hàm này trong thời gian o (n^(1/3 + o (1))), xem Phần 2.1 trên các trang 8-9 của:

http://arxiv.org/abs/1009.3956

Thuật toán liên quan đến việc cắt vùng thành các khoảng đủ mỏng và ước tính giá trị trên mỗi khoảng, trong đó các khoảng được chọn đủ mỏng để ước tính sẽ chính xác khi được làm tròn đến số nguyên gần nhất. Vì vậy, bạn tính toán trực tiếp lên đến một số phạm vi (họ đề xuất 100n^(1/3) nhưng bạn có thể sửa đổi điều này một cách cẩn thận) và sau đó thực hiện phần còn lại trong các lát mỏng này.

Xem mục OEIS để biết thêm thông tin về chuỗi này.

EDIT: Bây giờ tôi thấy Kerrek SB đề cập đến thuật toán này trong các bình luận. Tuy nhiên, một cách công bằng, tôi đã thêm nhận xét vào OEIS 5 năm trước vì vậy tôi không cảm thấy tồi tệ khi đăng câu trả lời 'của anh ấy. :)

Tôi cũng nên đề cập rằng không thể có thuật toán O (1), vì câu trả lời là xung quanh n log n và do đó viết nó ra cũng cần có thời gian> log n.

Đã trả lời ngày 4 tháng 1 năm 2015 lúc 19:03Jan 4, 2015 at 19:03

CharlescharlesCharles

11K13 Huy hiệu vàng64 Huy hiệu bạc100 Huy hiệu đồng13 gold badges64 silver badges100 bronze badges

2

Hãy chia tất cả số {1, 2, 3, ..., n} thành 2 nhóm: nhỏ hơn hoặc bằng sqrt(n) và lớn hơn sqrt(n). Đối với nhóm đầu tiên, chúng ta có thể tính tổng bằng cách lặp đơn giản. Đối với nhóm thứ hai, chúng ta có thể sử dụng quan sát sau: nếu

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

1, hơn

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

2. Đó là lý do tại sao chúng ta có thể lặp lại giá trị của

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

3 (từ

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

4 đến sqrt(n)) và tính toán số lượng

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

6 đó

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

3. Nó có thể được tìm thấy trong

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

8 cho một

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

9 cố định bằng cách sử dụng thực tế là

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

3 có nghĩa là

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))

1, cho

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))

2.

Các nhóm thứ nhất và thứ hai được xử lý trong O(sqrt(n)), tổng cộng cho O(sqrt(n)).

Đã trả lời ngày 4 tháng 1 năm 2015 lúc 18:21Jan 4, 2015 at 18:21

Krasnkevichkraskevichkraskevich

18.2K4 Huy hiệu vàng32 Huy hiệu bạc44 Huy hiệu đồng4 gold badges32 silver badges44 bronze badges

0

Đối với

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))

5 lớn, hãy sử dụng công thức:

ở đâu

(là một số siêu việt.)

is a transcendental number.)

Xem bài viết liên tục Euler-Mascheroni để biết thêm thông tin.

Đã trả lời ngày 4 tháng 1 năm 2015 lúc 18:12Jan 4, 2015 at 18:12

Danny Daglasdanny DaglasDanny Daglas

1.5011 huy hiệu vàng9 Huy hiệu bạc9 Huy hiệu đồng1 gold badge9 silver badges9 bronze badges

7

Bạn có thể nhận thấy rằng có các giá trị duy nhất O (n^(1/2)) trong tập s = {⌊n/1⌋, ⌊n/2⌋, ..., ⌊n/(n-1) ⌋, ⌊N/n⌋}. Do đó, bạn có thể tính toán hàm trong O (n^(1/2))

Ngoài ra vì hàm này không đối xứng, bạn thậm chí có thể tính toán x2 nhanh hơn bằng cách sử dụng công thức này: d (n) = σ (x = 1-> u) (⌊n/x⌋) - u^2 cho u = ⌊n^( 1/2)

Thậm chí phức tạp hơn nhưng nhanh hơn: Sử dụng phương pháp mà Richard Sladkey mô tả trong bài viết này, bạn có thể tính toán hàm trong O (n^(1/3))

Đã trả lời ngày 26 tháng 8 năm 2021 lúc 20:22Aug 26, 2021 at 20:22

1