No.1966 Median of Divisors

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 87
作問者 :

MasKoaTS / テスター :

Shirotsume

2 ProblemId : 7667 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2024-11-28 22:38:53

正整数 $N$ , $M$ が与えられます。ただし、 $M$ は偶数とします。

$1$ 以上 $N^{M}$ 以下の整数 $x$ のうち、次のように定義される $f(x)$ に対して $f(x) > \sqrt{x}$ を満たすものの総和を求めてください。

$x$ の正の約数の中央値を $f(x)$ とする。

厳密には、 $x$ の正の約数の個数を $k$ とし、 $x$ の正の約数すべてを値の小さい順に並べ替えたものを $a_{1}, a_{2}, \dots, a_{k}$ として、 $f(x)$ を次のように定義する。
- $\displaystyle f(x) := \left\{ \begin{array}{l} \displaystyle a_{ \frac{ k + 1 }{ 2 } } \text{ （$k$ が奇数のとき）} \\ \displaystyle \frac{ 1 }{ 2 } \left( a_{ \frac{ k }{ 2 } } + a_{ \frac{ k + 2 }{ 2 } } \right) \text{ （$k$ が偶数のとき）} \\ \end{array} \right.$

答えは非常に大きくなる可能性があるので、 $10^{9}+7$ で割った余りを出力してください。

$T$ 個のテストケースについて答えを求めてください。

まず、 $1$ 行目にはテストケースの個数 $T$ が与えられます。

$T$

続けて $T$ 個のテストケースがそれぞれ次の形式で与えられます。

 $N$   $M$

$(i+1)$ $(1 \leq i \leq T)$ 行目には、 $i$ 個目のテストケースにおける $N$ と $M$ の値がこの順に半角スペース区切りで与えられます。

答えを $1$ 行ずつ合計 $T$ 行に出力し、最後に改行してください。

$i$ $(1 \leq i \leq T)$ 行目には、 $i$ 個目のテストケースにおける答えを出力してください。

10
2 2
9 4
1 13815080
5694830 3748
15 3220
173991719 37288
7 37682
13868805 2400766
37236186 5850
1181 334

例えば $1$ つ目のテストケースでは、 $1$ 以上 $2^{2} = 4$ 以下の整数について、

$1$ の正の約数は $1$ のみであり、 $\displaystyle f(1) = 1 \leq \sqrt{1}$
$2$ の正の約数は $1, 2$ の $2$ 個であり、 $\displaystyle f(2) = \frac{1+2}{2} = \frac{3}{2} > \sqrt{2}$
$3$ の正の約数は $1, 3$ の $2$ 個であり、 $\displaystyle f(3) = \frac{1+3}{2} = 2 > \sqrt{3}$
$4$ の正の約数は $1, 2, 4$ の $3$ 個であり、 $\displaystyle f(4) = 2 \leq \sqrt{4}$

なので、条件を満たす $x$ は $2$ , $3$ のみであり、これらの総和は $5$ となります。

残りのテストケースについても同様に総和を求め、 $10^{9}+7$ で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。