Số rất lẻ (2.5 điểm)
View as PDFMột số nguyên dương ~m > 1~ được gọi là số "rất lẻ" nếu các ước dương của ~m~ (kể cả chính nó) có thể được viết lên một vòng tròn theo thứ tự nào đó sao cho tổng của hai số đứng cạnh nhau luôn là số lẻ. Ngoài ra, tổng của tất cả các ước dương của ~m~ cũng phải là số lẻ.
Ví dụ, số ~18~ là số rất lẻ vì các ước dương của ~18~ là ~1,2,3,6,9,18~. Ta có thể viết các số này lên vòng tròn theo thứ tự trên, khi đó tổng của hai số đứng cạnh nhau luôn là số lẻ, và tổng tất cả các ước là ~1 + 2 + 3 + 6 + 9 + 18 = 39~ cũng là số lẻ.
Yêu cầu: Cho ~q~ truy vấn, mỗi truy vấn gồm một số nguyên dương ~n~: hãy in ra số lượng số rất lẻ là ước của ~n~.
Dữ liệu
Cho trong file văn bản VERYODD.INP,
- Dòng đầu tiên chứa số nguyên dương ~q~ (~1 \le q \le 10~).
- Trong ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ (~1 \le n \le 10^{18}~).
Kết quả
Ghi ra file văn bản VERYODD.OUT tất cả ~q~ dòng, dòng thứ ~i~ là câu trả lời cho truy vấn thứ ~i~.
Ví dụ
| VERYODD.INP | VERYODD.OUT | Giải thích |
|---|---|---|
| ~3~ ~18~ ~30~ ~7~ |
~2~ ~1~ ~0~ |
Với ~n = 18~ thì có các số rất lẻ là ~2~ và ~18~ nên đáp án là ~2~. Với ~n = 30~ thì chỉ có một ước rất lẻ là ~2~. Với ~n = 7~, không có ước dương nào là số rất lẻ. |
Ràng buộc
- ~20\%~ số điểm tương ứng với các test thỏa mãn ~n \le 10^3~.
- ~25\%~ số điểm tương ứng với các test thỏa mãn ~n \le 10^6~.
- ~25\%~ số điểm tương ứng với các test thỏa mãn ~n \le 10^{12}~.
- ~30\%~ số điểm còn lại không có ràng buộc nào thêm.
Comments