問題一覧 > 通常問題

No.1844 Divisors Sum Sum

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 125
作問者 : 👑 potato167potato167 / テスター : 👑 tatyamtatyam ramdosramdos
2 ProblemId : 6887 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-02-18 18:37:54

問題文

以下の問題 $X$ について考えます。

問題 $X$

与えられた整数について、その整数の正の約数の和を求めてください。

長さ $L$ の整数列 $P$ と $e$ が与えられます。 $P$ の要素は相異なる素数です。 ここで、 $N=\prod_{i=1}^{L} P_i^{e_i}$ $(= P_1^{e_1}\times P_2^{e_2}\times \dots \times P_L^{e_L})$ とします。

$N$ の正の約数全てについて、その数を与えたときの問題 $X$ の答えを求め、その和を出力してください。ただし、答えが非常に大きくなることがあるので、 $(10^{9}+7)$ で割ったあまりを出力してください。

制約

  • $1\leq L\leq 2\times10^{5}$
  • $1\leq P_i,e_i\leq 10^{9}$
  • 入力は全て整数
  • $P_i$ は全て素数
  • $i\neq j$ ならば $P_i\neq P_j\;(1\leq i,j\leq L)$

入力

$L$
$P_1\; e_1$
$P_2\; e_2$
$\vdots$
$P_L\; e_L$

出力

答えを $(10^{9}+7)$ で割ったあまりを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
2
2 2
3 1
出力
55

$N=2^{2}\times3^{1}=12$ であり、$12$ の約数は $1,2,3,4,6,12$ の $6$ 個です。

  • $1$ の約数の和 : $1=1$
  • $2$ の約数の和 : $1+2=3$
  • $3$ の約数の和 : $1+3=4$
  • $4$ の約数の和 : $1+2+4=7$
  • $6$ の約数の和 : $1+2+3+6=12$
  • $12$ の約数の和 : $1+2+3+4+6+12=28$

よって、出力すべき値は、$1+3+4+7+12+28=55$ となります。

サンプル2
入力
1
167 1
出力
169
サンプル3
入力
10
914260891 350096548
887686339 192497607
786328273 878092875
735623069 355760739
129154631 798229587
427094807 82130028
520933789 204087959
641996039 29097051
278883373 321445979
447005677 226153917
出力
326821356

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