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