Tổng Bình Phương & Đếm Ước Số O(√N)

Buổi 57 — Sàng & Euler Totient Mathematics Number Theory
Points
10
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
loop
Submissions
Đề bài

Cho số nguyên dương N (1 ≤ N ≤ 10^12). Hãy đếm tổng số lượng ước nguyên dương của N.

Dữ liệu vào (Input)
  • Một dòng duy nhất chứa số nguyên dương N (1 ≤ N ≤ 10^12).
Dữ liệu ra (Output)
  • In ra một số nguyên duy nhất là số lượng ước nguyên dương của N.
Ví dụ mẫu
Sample Input 1
12
Sample Output 1
6
Sample Input 2
36
Sample Output 2
9
Gợi ý thuật toán

Duyệt i từ 1 đến i * i ≤ N. Nếu N % i == 0:

  • Nếu i * i == N thì tăng biến đếm thêm 1.
  • Ngược lại tăng biến đếm thêm 2 (gồm ước i và ước N / i).
Draft saved