Trại hè Phương Nam 2024 - Ước số

Điểm: 800 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 1G

Input: DIV.INP

Output: DIV.OUT

Tác giả:

remyvnkhiemtruong

Dạng bài

Ngôn ngữ cho phép

C, C++, Pascal, ~~pypy~~, ~~pypy3~~, Python

Các ước số tự nhiên có vai trò quan trọng trong nhiều thuật toán mã hóa, chẳng hạn như RSA, một thuật toán mã hóa công khai phổ biến. Việc tạo ra dãy các ước số của một tập hợp số tự nhiên có thể giúp hiểu được cách các ước số phân phối và ảnh hưởng đến tính bảo mật của mã hóa. Là một người yêu thích môn mật mã, Nam quan sát đặc điểm các ước số của một tập hợp số tự nhiên thông qua bài toán sau.

Nam có một dãy số $A$ gồm $N$ phần tử, mỗi phần tử là một số tự nhiên khác $0$ . Gọi $D$ là dãy các phần tử có giá trị không giảm gồm tất cả các ước số tự nhiên, không nhất thiết phải phân biệt của các phần tử của $A$ . Nam chuẩn bị dãy $P$ gồm $Q$ số tự nhiên khác $0$ , mỗi số biểu thị một vị trí trong dãy $D$ . Do dãy $D$ chưa được cho trước mà phải tính toán thông qua các giá trị trong dãy $A$ và $N$ , Nam mong muốn xác định nhanh từng giá trị phần tử trong dãy $D$ tương ứng với mỗi phần tử thuộc dãy $P$ . Ví dụ: với $N = 4$ , $A = (10, 2, 5, 2)$ và $P = (5, 1, 10)$ , ta có dãy $D = (1, 1, 1, 1, 2, 2, 2, 5, 5, 10)$ và các giá trị phần tử trong dãy $D$ tương ứng với mỗi phần tử thuộc dãy $P$ là $(2, 1, 10)$ .

Yêu cầu: Hãy giúp Nam xác định từng phần tử trong dãy $D$ tương ứng với với mỗi phần tử trong dãy $P$ .

Input, Output

Input: (DIV.INP)

Vào từ file văn bản DIV.INP:

Dòng đầu tiên chứa hai số nguyên dương $N$ và $Q$ lần lượt là số lượng phần tử dãy $A$ và số lượng phần tử dãy $P$ ( $1 \le N \le 10^6$ ; $1 \le Q \le 10^5$ ).
Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2,..., A_N$ mô tả dãy $A$ ( $1 \le A_i \le 10^6$ ).
Dòng thứ ba chứa $Q$ số nguyên dương $P_1, P_2,..., P_Q$ mô tả dãy $P$ ( $1 \le P_i \le |D|$ , với $|D|$ là số lượng phần tử dãy $D$ ).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output: (DIV.OUT)

Ghi ra file văn bản DIV.OUT duy nhất một dòng gồm $Q$ số nguyên, cách nhau bởi dấu cách, là các phần tử trong dãy $D$ tương ứng với các phần tử trong dãy $P$ .

Sample

Subtask

Có $25\%$ số test ứng với $25\%$ số điểm của bài thoả mãn: $N, Q \le 1000$ ; $A_i \le 1000$ với mọi $1 \le i \le N$ ; $P_i \le 1000$ với mọi $1 \le i \le Q$ .
$25\%$ số test khác ứng với $25\%$ số điểm của bài thoả mãn: $A_i$ là số nguyên tố với mọi $1 \le i \le N$ .
$20\%$ số test khác ứng với $20\%$ số điểm của bài thoả mãn: $N \le 10 000$ ; $P_i \le 2 · 10^6$ với mọi $1 \le i \le Q$ .
$20\%$ số test khác ứng với $20\%$ số điểm của bài thoả mãn: $P_i \le 2·10^6$ với mọi $1 \le i \le Q$ .
$10\%$ test còn lại ứng với $10\%$ số điểm của bài: Không có ràng buộc gì thêm.

Bình luận đầu tiên

Bình luận

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