CSES - Counting Divisor | Đếm ước
Xem PDF
Đ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
import sys
import math
MAX = 10**6
divisors = [0] * (MAX + 1)
for i in range(1, MAX + 1):
for j in range(i, MAX + 1, i):
divisors[j] += 1
input = sys.stdin.read
data = input().split()
n = int(data[0])
results = []
for i in range(1, n + 1):
x = int(data[i])
results.append(str(divisors[x]))
sys.stdout.write("\n".join(results) + "\n")
Giải thích:
Giải thích đoạn mã:
Khởi tạo mảng divisors:
divisors[j] lưu trữ số lượng ước của số j.
divisors có kích thước từ 0 đến 10^6.
Tính toán số lượng ước:
Vòng lặp đầu tiên: Với mỗi số i từ 1 đến MAX, bạn sẽ đi qua các bội số của i và tăng giá trị của divisors[j] (nơi j là các bội số của i).
Đọc dữ liệu đầu vào:
input = sys.stdin.read sẽ đọc tất cả các dòng đầu vào cùng một lúc, sau đó chia nhỏ thành danh sách các chuỗi qua split().
Xử lý các yêu cầu:
Duyệt qua từng số trong danh sách và tìm số lượng ước của nó từ mảng divisors, sau đó lưu trữ vào results.
In kết quả:
Kết quả được nối lại thành một chuỗi lớn và in ra một lần duy nhất, giúp tiết kiệm thời gian in
-
0
kukuku12345
9:07 p.m. 20 Tháng 10, 2024
11 bình luận nữachép chat rồi còn đăng