No.1791 Repeat Multiplication
ripity
ramdosNote
The time limit is 3 seconds.
AC has been confirmed with C++, PyPy3 (not Python), Java, and Ruby, but there is no guarantee that AC can be obtained with other languages.
Problem Statement
Consider performing the following operation $0$ or more times on the sequence $A=(1)$.
- Let $a$ be the last element of $A$. Choose $1$ integer $b$ satisfying all of the following conditions and append it to the end of $A$.
- $a\lt b\le N$
- $b$ is a multiple of $a$
Input
$N\ Q$ $x_1$ $x_2$ $\vdots$ $x_Q$
- $1\le N\le 1.5\times 10^6$
- $1\le Q\le \min(N,10^5)$
- $1\le x_i\le N$
- $x_i\neq x_j$ if $i\neq j$
- All input values are integers.
Output
Print $Q$ lines in total.
On the $i$-th line, print the answer to the $i$-th query.
Sample
Sample 1
Input
6 6 1 2 3 4 5 6
Output
9 3 2 2 1 3
The sequences that can be made by the operations are the following: $(1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,2,4),(1,2,6),(1,3,6)$, which is $9$ sequences.
The sequences $A$ containing $1$ are all of the above. Thus, the answer for $i=1$ is $9$.
The sequences $A$ containing $2$ are $(1,2),(1,2,4),(1,2,6)$. Thus, the answer for $i=2$ is $3$.
The sequences $A$ containing $3$ are $(1,3),(1,3,6)$. Thus, the answer for $i=3$ is $2$.
The sequences $A$ containing $4$ are $(1,4),(1,2,4)$. Thus, the answer for $i=4$ is $2$.
The sequences $A$ containing $5$ are $(1,5)$. Thus, the answer for $i=5$ is $1$.
The sequences $A$ containing $6$ are $(1,6),(1,2,6),(1,3,6)$. Thus, the answer for $i=6$ is $3$.
Sample 2
Input
10 4 1 2 3 10
Output
19 6 3 3
Sample 3
Input
2021 2 12 20
Output
18472 7600
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。