Tất cả thử thách
Khó 0 đã giải Tỷ lệ chấp nhận 0%

Tổng các số không phải tổng hai số dư thừa

Cộng các số không vượt quá giới hạn mà không viết được thành tổng của hai số dư thừa.

Bạn sẽ học được gì

  • Tính tổng ước cho cả một đoạn bằng sàng
  • Đánh dấu các tổng đạt được bằng mảng boolean
  • Dừng sớm vòng lặp lồng nhau khi tổng vượt giới hạn

Đề bài

Xem bản gốc (English)

Một số được gọi là số dư thừa (abundant number) khi tổng các ước thực sự của nó (mọi ước trừ chính nó) lớn hơn nó. 12 là số nhỏ nhất như vậy: 1 + 2 + 3 + 4 + 6 = 16. Có những số viết được thành tổng của hai số dư thừa (một số có thể dùng hai lần, như 24 = 12 + 12), có những số thì không. Hãy cộng tất cả các số nguyên dương từ 1 đến limit không viết được như vậy.

Hãy viết non_abundant_sums(limit).

Dùng sàng để tính tổng ước của mọi số cùng một lúc, liệt kê các số dư thừa, rồi đánh dấu mọi tổng của từng cặp còn nằm trong giới hạn.

Đầu vào

limit: Số lớn nhất cần kiểm tra.

Đầu ra

Trả về tổng của mọi n với 1 ≤ n ≤ limit không phải là tổng của hai số dư thừa.

Ràng buộc

1 ≤ limit ≤ 10,000

Ví dụ

Ví dụ 1
Đầu vào:
limit = 23

Kết quả mong đợi:
expected = 276
Đầu vào:
long long limit = 23;

Kết quả mong đợi:
long long expected = 276;
Đầu vào:
long limit = 23;

Kết quả mong đợi:
long expected = 276;

Giải thích

Không có hai số dư thừa nào có tổng nhỏ hơn hoặc bằng 23, nên mọi số đều được tính: 1 + 2 + ... + 23 = 276.

Ví dụ 2
Đầu vào:
limit = 30

Kết quả mong đợi:
expected = 411
Đầu vào:
long long limit = 30;

Kết quả mong đợi:
long long expected = 411;
Đầu vào:
long limit = 30;

Kết quả mong đợi:
long expected = 411;

Giải thích

24 = 12 + 12 và 30 = 12 + 18 bị loại, nên đáp án là 465 − 24 − 30 = 411.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Với mỗi i, cộng i vào tổng ước của 2i, 3i, 4i, ...

Gợi ý 2

Thu thập các số dư thừa theo thứ tự tăng dần.

Gợi ý 3

Với mỗi cặp a ≤ b, dừng vòng lặp trong khi a + b vượt quá giới hạn.

Độ phức tạp mong đợi

thời gian O(limit log limit + A²) với A là số lượng số dư thừa, bộ nhớ phụ O(limit)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.