Đếm Ước Giới Hạn

Tác giả:

Dạng bài

Điểm: 100 Thời gian: 5.0s Bộ nhớ: 1000M Input: bàn phím Output: màn hình

Cho một số nguyên \(N\). Ta xét dãy số \(\mathcal{S}\) là tập hợp các số nguyên từ \(1\) đến \(N\), tức là \(\mathcal{S} = \{1, 2, \dots, N\}\).

Cho \(Q\) truy vấn, mỗi truy vấn là một số nguyên \(a\).

Với mỗi truy vấn \(a\), bạn cần đếm xem có bao nhiêu số \(x\) trong dãy \(\mathcal{S}\) (thỏa mãn \(1 \le x \le N\)) là ước số của \(a\).

Input

Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N \le 10^6\), \(1 \le Q \le 10^7\)).
\(Q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(a\) (\(1 \le a \le 10^6\)), là một truy vấn.

Test 1

Input

Output

5
4
2

Explanation

Dãy số \(\mathcal{S}\) là \(\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\) (vì \(N=10\)).

Truy vấn 1 (\(a=100\)): Các ước số của 100 là \(\{1, 2, 4, 5, 10, 20, 25, 50, 100\}\). Trong số này, các số \(\le N=10\) là \(\{1, 2, 4, 5, 10\}\). Có 5 số.
Truy vấn 2 (\(a=10\)): Các ước số của 10 là \(\{1, 2, 5, 10\}\). Cả 4 số này đều \(\le N=10\). Có 4 số.
Truy vấn 3 (\(a=7\)): Các ước số của 7 là \(\{1, 7\}\). Cả 2 số này đều \(\le N=10\). Có 2 số.

Test 2

Input

100 2
60
12

Output

12
6

Explanation

Dãy số \(\mathcal{S}\) là \(\{1, 2, \dots, 100\}\) (vì \(N=100\)).

Truy vấn 1 (\(a=60\)): Các ước của 60 là \(\{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60\}\). Tất cả 12 ước này đều \(\le N=100\). Có 12 số.
Truy vấn 2 (\(a=12\)): Các ước của 12 là \(\{1, 2, 3, 4, 6, 12\}\). Tất cả 6 ước này đều \(\le N=100\). Có 6 số.

Không có bình luận nào.