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

Cặp số thân thiết

Liệt kê mọi cặp số thân thiết có cả hai số đều không vượt quá một giới hạn.

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

  • Lập bảng tổng ước thực sự cho mọi số đến một giới hạn
  • Kiểm tra điều kiện của cặp theo cả hai chiều
  • Tránh liệt kê một cặp hai lần hoặc liệt kê số hoàn hảo

Đề bài

Xem bản gốc (English)

Gọi s(n) là tổng các ước thực sự của n (các ước của nó, trừ chính n). Hai số khác nhau a và b tạo thành một cặp số thân thiết khi s(a) = b và s(b) = a. Cặp nhỏ nhất là 220 và 284: s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 và s(284) = 1 + 2 + 4 + 71 + 142 = 220.

Hãy viết amicable_pair(limit).

Tính s(n) lần lượt cho từng n đến limit sẽ rất chậm. Dùng phương pháp sàng sẽ tốt hơn: với mỗi d, cộng d vào mọi bội số của d lớn hơn d.

Đầu vào

limit: Giá trị lớn nhất mà mỗi số trong cặp được phép có.

Đầu ra

Trả về danh sách các cặp [a, b] với a < b ≤ limit, sắp xếp theo a tăng dần. Một cặp chỉ được đưa vào khi cả hai số đều không vượt quá limit. Số hoàn hảo (có s(n) = n) không tạo thành cặp. Nếu không có cặp nào, trả về danh sách rỗng.

Ràng buộc

1 ≤ limit ≤ 200,000

Ví dụ

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

Kết quả mong đợi:
expected = [
    [220, 284],
    [1184, 1210]
]
Đầu vào:
long long limit = 1500;

Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {
    {220, 284},
    {1184, 1210}
};
Đầu vào:
long limit = 1500;

Kết quả mong đợi:
long[][] expected = new long[][] {
    new long[] {220, 284},
    new long[] {1184, 1210}
};

Giải thích

s(220) = 284 và s(284) = 220, s(1184) = 1210 và s(1210) = 1184. Cả hai cặp đều nằm trong phạm vi 1500: [[220, 284], [1184, 1210]].

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

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

Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {};
Đầu vào:
long limit = 250;

Kết quả mong đợi:
long[][] expected = new long[][] {};

Giải thích

220 không vượt quá 250, nhưng số đi cặp với nó là 284 thì vượt, nên không có cặp nào: [].

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 d từ 1 đến limit / 2, cộng d vào tổng ước của 2d, 3d, 4d, ...

Gợi ý 2

Với mỗi a, gọi b là tổng ước của nó, rồi kiểm tra b nằm trong phạm vi và tổng ước của b bằng a.

Gợi ý 3

Yêu cầu a < b giúp mỗi cặp chỉ được liệt kê một lần và tự động bỏ qua số hoàn hảo.

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

thời gian O(limit log limit), 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.