CSES - Counting Divisor | Đếm ước

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Thời gian:
Pypy 3 1.5s
Python 3 3.5s
Tác giả:
Flower_On_Stone , Phuc_QrdA5
Dạng bài
Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho \(n\) số nguyên. Với mỗi số, hãy cho biết số lượng ước của nó.

Ví dụ, nếu \(x = 18\), câu trả lời đúng là \(6\) vì các ước của nó là \(1,2,3,6,9,18.\)

Input

  • Dòng đầu tiên chứa một số nguyên \(n\)
  • Sau đó là \(n\) dòng, mỗi dòng chứa một số nguyên \(x\)

Output

  • Đối với mỗi số nguyên, in ra số lượng ước của nó.

Constraints

  • \(1 \leq n \leq 10^5\)
  • \(1 \leq x \leq 10^6\)

Example

Sample input

3
16
17
18

Sample output

5
2
6

Bình luận

  • danh3003 • 4:38 p.m. 9 Tháng 1, 2025 •

    Lưu ý cho những ai làm bài này chưa AC:

    • Khi duyệt qua các số từ \(1\) -> \(\sqrt{x}\), ta nên dùng:
      C++
      for (int i = 1; i * i < x; i++){
    //Thuật toán tính số ước mà không kiểm tra x là số chính phương
}if ((int) sqrt(x) == sqrt(x)){
    //Cộng thêm 1 vào bước đếm
}

      Thay vì:
      C++
      for (int i = 1; i <= pow(x, 0.5); i++){
    //Thuật toán tính số ước mà cần kiểm tra x là số chính phương
}

      Nguyên do:
      • Nếu mỗi lần lặp đều cần kiểm tra x là số chính phương thì độ phức tạp sẽ cộng thêm \(\sqrt{x}\) \(\Rightarrow\) kiểm tra x là số chính phương ở cuối. Nếu \(x = a^2\) thì biến đếm \(+1\).
      • Hàm \(sqrt()\) được tạo ra để chuyên dùng tính \(\sqrt{x}\) nên sẽ có khả năng tính toán nhanh hơn hàm \(pow(x, 0.5)\).
    0
    Phản hồi
      • 12 bình luận nữa