Khó 0 đã giải Tỷ lệ chấp nhận 0%

Non-Abundant Sums

Add up the numbers up to a limit that cannot be written as the sum of two abundant numbers.

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

  • Compute divisor sums for a range with a sieve
  • Mark reachable sums with a boolean array
  • Cut a double loop short once sums pass the limit

Đề bài

Xem bản dịch

A number is abundant when its proper divisors (all divisors except itself) add up to more than it. 12 is the smallest: 1 + 2 + 3 + 4 + 6 = 16. Some numbers can be written as the sum of two abundant numbers (the same one may be used twice, as in 24 = 12 + 12) and some cannot. Add up every positive integer from 1 to limit that cannot.

Implement non_abundant_sums(limit).

Find the divisor sums for every number at once with a sieve, list the abundant numbers, then mark every pair sum that stays within the limit.

Input

limit: The largest number to check.

Output

Return the sum of all n with 1 ≤ n ≤ limit that are not the sum of two abundant numbers.

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

No two abundant numbers add up to 23 or less, so every number counts: 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 and 30 = 12 + 18 are left out, so the answer is 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

For each i, add i to the divisor sum of 2i, 3i, 4i, ...

Gợi ý 2

Collect the abundant numbers in increasing order.

Gợi ý 3

For each pair a ≤ b, stop the inner loop once a + b passes the limit.

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

O(limit log limit + A²) time for A abundant numbers, O(limit) extra space

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.