STRNO - Strange Number

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: bạn được cho 2 số nguyên dương X và K. Xác định xem tồn tại một số nguyên dương A sao cho A có đúng X ước số, trong X ước số đó có K ước số là số nguyên tố.

Ví dụ: với X = 4, K = 2, ta có thể tìm được A = 6. Số 6 có 4 ước (1, 2, 3, 6), trong đó 2 ước (2, 3) là số nguyên tố.

Hướng dẫn giải:

Lý thuyết: Phân tích một số nguyên A ra thừa số nguyên tố  (với p là một số nguyên tố). Khi đó tổng số ước N bằng .

Ở đây A chỉ có đúng K ước nguyên tố, nghĩa là trong đa thức   tồn tại ít nhất K đa thức có dạng . Để giải được bài này, ta cần phải đếm xem có thể phân tích X thành số nguyên tố bao nhiêu lần. Mỗi số nguyên tố của X sau khi phân tích sẽ ứng với một đa thức  , và nếu tổng số đa thức >= K thì ta có thể xây dựng được số A.

Code mẫu (C++)

Happy coding!