Đề bài
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ụ
Đầ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.
Đầ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.