Đề bài
Các ước thực sự của n là những ước dương của nó, trừ chính n. Hãy so sánh tổng các ước này với n: nếu tổng lớn hơn thì đó là số dồi dào (abundant), nếu bằng thì là số hoàn hảo (perfect), còn nếu nhỏ hơn thì là số khuyết (deficient). Ví dụ, các ước thực sự của 12 là 1, 2, 3, 4 và 6, có tổng là 16, nên 12 là số dồi dào.
Hãy viết abundant_perfect_deficient(n).
n có thể lớn tới 10^12, nên việc thử mọi số nhỏ hơn n là quá chậm. Các ước số luôn đi theo cặp d và n / d, nên bạn chỉ cần thử d đến √n.
Đầu vào
n: Số cần phân loại.
Đầu ra
Trả về chuỗi "abundant", "perfect" hoặc "deficient", viết thường. Số 1 không có ước thực sự nào (tổng bằng 0), nên là số khuyết.
Ràng buộc
1 ≤ n ≤ 10^12
Ví dụ
Đầu vào:
n = 28
Kết quả mong đợi:
expected = "perfect"
Đầu vào:
long long n = 28;
Kết quả mong đợi:
std::string expected = "perfect";
Đầu vào:
long n = 28;
Kết quả mong đợi:
string expected = "perfect";
Giải thích
Các ước thực sự 1 + 2 + 4 + 7 + 14 có tổng là 28, nên kết quả là "perfect".
Đầu vào:
n = 15
Kết quả mong đợi:
expected = "deficient"
Đầu vào:
long long n = 15;
Kết quả mong đợi:
std::string expected = "deficient";
Đầu vào:
long n = 15;
Kết quả mong đợi:
string expected = "deficient";
Giải thích
Các ước thực sự 1 + 3 + 5 có tổng là 9, nhỏ hơn 15, nên kết quả là "deficient".
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Nếu d là ước của n thì n / d cũng vậy; chỉ cần lặp d khi d × d ≤ n.
Gợi ý 2
Khi d × d = n, chỉ cộng d một lần chứ không phải hai lần.
Gợi ý 3
Nhớ bỏ chính n ra khỏi tổng, và xử lý riêng trường hợp n = 1.
Độ phức tạp mong đợi
thời gian O(√n), bộ nhớ phụ O(1)
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.