Macarie

Time limit: 0.4s
Memory limit: 64MB
Input: macarie.in
Output: macarie.out

Macarie has received a new problem as part of his informatics assignment, and here is its statement:

We are given an array AA with NN positive integers. Let's consider the increasing array DD made of all positive divisors, not necessarily distinct of the values from AA. As an example, for N=4N=4 and A=(6,2,3,2)A=(6, 2, 3, 2), we have the array D=(1,1,1,1,2,2,2,3,3,6)D=(1,1,1,1,2,2,2,3,3,6).

Task

Given an array PozPoz made of QQ positive integers, representing positions from DD, find for each of the values, the value at the respective position from the array DD.

Input data

The first line of the input file macarie.in contains the integers NN and QQ.
The second line of the input contains NN positive integers, representing the values from AA.
The third line has QQ positive integers, representing the values from PozPoz. The numbers on the same line are separated by singular spaces.

Output data

The first line of the output file macarie.out contains QQ positive integers, separated by spaces, representing the values from DD, in order in which the positions show up in PozPoz.

Constraints and clarifications

  • 1N1 000 0001\leq N \leq 1 \ 000 \ 000, 1Q100 0001\leq Q \leq 100 \ 000;
  • The arrays AA, DD and PozPoz are indexed from 11.
  • 1Ai1 000 0001 \leq A_i \leq 1 \ 000 \ 000 for 1iN1 \leq i \leq N. The values from AA are not necessarily distinct.
  • 1PoziD1 \leq Poz_i \leq |D| for 1iQ1 \leq i \leq Q, wher D|D| is the length of DD.
# Score Constraints
1 23 All input values are 1 000\leq 1 \ 000
2 18 All values AiA_i are prime numbers
3 23 N10 000N \leq 10 \ 000, Pozi2 000 000Poz_i \leq 2 \ 000 \ 000
4 15 Pozi2 000 000Poz_i\leq 2 \ 000 \ 000
5 21 No additional constraints.

Example 1

macarie.in

4 5 
32 42 49 21
2 5 9 7 17

macarie.out

1 2 4 3 21

Explanation

N=4N = 4 and Q=5Q = 5. A=(32,42,49,21)A = (32, 42, 49, 21) and D=(1,1,1,1,2,2,3,3,4,6,7,7,7,8,14,16,21,21,32,42,49)D = (1, \underline{1}, 1, 1, \underline{2}, 2, \underline{3}, 3, \underline{4}, 6, 7, 7, 7, 8, 14, 16, \underline{21}, 21, 32, 42, 49).

Example 2

macarie.in

5 4
24 56 8 490 28
35 25 28 38

macarie.out

70 12 14 490

Explanation

N=5N = 5, Q=4Q = 4 and D[35]=70D[35] = 70, D[25]=12D[25] = 12, D[28]=14D[28] = 14, D[38]=490D[38] = 490.

Problem info

ID: 2501

Editors:

Author:

Source: OJI 2024 IX: Problema 1

Tags:

OJI 2024 IX

Log in or sign up to be able to send submissions!