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

Số dồi dào, số hoàn hảo hay số khuyết

Phân loại một số là số dồi dào, số hoàn hảo hay số khuyết dựa vào tổng các ước thực sự của nó.

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

  • Tính tổng các ước thực sự trong thời gian O(√n)
  • Tránh cộng hai lần ước bằng căn bậc hai
  • Trả về một trong ba nhãn dựa trên phép so sánh

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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".

Ví dụ 2
Đầ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.

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.