問題一覧 > 通常問題

No.1791 Repeat Multiplication

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 : ripityripity / テスター : ramdosramdos
0 ProblemId : 7339 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-19 00:20:43

注意

実行時間制限は3秒です。
C++、PyPy3(Pythonではない)、Java、RubyでのACが確認できていますが、その他の言語でACをとれる保証はありません。

問題文

数列 $A=(1)$ に対して以下の操作を $0$ 回以上行うことを考えます。

  • $A$ の末尾の項を $a$ とする。以下の条件をすべて満たす整数 $b$ を $1$ つ選び、 $A$ の末尾に追加する。
    • $a\lt b\le N$
    • $b$ は $a$ の倍数である
$Q$ 個のクエリが与えられます。 $i$ 個目のクエリでは整数 $x_i$ が与えられるので、操作によって作ることができる $A$ であって $x_i$ を含むものの個数を求めてください。

入力

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。