No.1791 Repeat Multiplication
タグ : / 解いたユーザー数 55
作問者 :
ripity
/ テスター :
ramdos
注意
実行時間制限は3秒です。
C++、PyPy3（Pythonではない）、Java、RubyでのACが確認できていますが、その他の言語でACをとれる保証はありません。
問題文
数列 $A=(1)$ に対して以下の操作を $0$ 回以上行うことを考えます。
- $A$ の末尾の項を $a$ とする。以下の条件をすべて満たす整数 $b$ を $1$ つ選び、 $A$ の末尾に追加する。
- $a\lt b\le N$
- $b$ は $a$ の倍数である
入力
$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$
- $i\neq j$ ならば $x_i\neq x_j$
- 入力はすべて整数で与えられる
出力
合計 $Q$ 行出力してください。
$i$ 行目には $i$ 個目のクエリの答えを出力してください。
サンプル
サンプル1
入力
6 6 1 2 3 4 5 6
出力
9 3 2 2 1 3
操作によって作ることができる数列は $(1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,2,4),(1,2,6),(1,3,6)$ の $9$ 個です。
$1$ が含まれる $A$ は 上記のすべてです。よって、$i=1$ のときの答えは $9$ です。
$2$ が含まれる $A$ は $(1,2),(1,2,4),(1,2,6)$ です。よって、$i=2$ のときの答えは $3$ です。
$3$ が含まれる $A$ は $(1,3),(1,3,6)$ です。よって、$i=3$ のときの答えは $2$ です。
$4$ が含まれる $A$ は $(1,4),(1,2,4)$ です。よって、$i=4$ のときの答えは $2$ です。
$5$ が含まれる $A$ は $(1,5)$ です。よって、$i=5$ のときの答えは $1$ です。
$6$ が含まれる $A$ は $(1,6),(1,2,6),(1,3,6)$ です。よって、$i=6$ のときの答えは $3$ です。
サンプル2
入力
10 4 1 2 3 10
出力
19 6 3 3
サンプル3
入力
2021 2 12 20
出力
18472 7600
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。