問題一覧 > 通常問題

No.1966 Median of Divisors

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 71
作問者 : MasKoaTSMasKoaTS / テスター : ShirotsumeShirotsume
2 ProblemId : 7667 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-05 21:06:45

問題文

正整数 $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 \leq T \leq 10^{5}$

  • $1 \leq N, M \leq 10^{9}$

  • $T$, $N$ は整数

  • $M$ は偶数

入力

まず、$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$ 個目のテストケースにおける答えを出力してください。

サンプル

サンプル1
入力
10
2 2
9 4
1 13815080
5694830 3748
15 3220
173991719 37288
7 37682
13868805 2400766
37236186 5850
1181 334
出力
5
21346200
0
630387477
322736621
782465690
423690148
362798159
283023473
859877451

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