問題一覧 > 通常問題

No.1844 Divisors Sum Sum

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 128
作問者 : 👑 potato167 / テスター : tatyam ramdos
3 ProblemId : 6887 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-08 00:12:05

問題文

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

問題 XX

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

長さ LL の整数列 PP と ee が与えられます。 PP の要素は相異なる素数です。 ここで、 N=∏i=1LPieiN=\prod_{i=1}^{L} P_i^{e_i} (=P1e1×P2e2×⋯×PLeL)(= P_1^{e_1}\times P_2^{e_2}\times \dots \times P_L^{e_L}) とします。

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

制約

  • 1≤L≤2×1051\leq L\leq 2\times10^{5}
  • 1≤Pi,ei≤1091\leq P_i,e_i\leq 10^{9}
  • 入力は全て整数
  • PiP_i は全て素数
  • i≠ji\neq j ならば Pi≠Pj  (1≤i,j≤L)P_i\neq P_j\;(1\leq i,j\leq L)

入力

LL
P1  e1P_1\; e_1
P2  e2P_2\; e_2
⋮\vdots
PL  eLP_L\; e_L

出力

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

サンプル

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

N=22×31=12N=2^{2}\times3^{1}=12 であり、1212 の約数は 1,2,3,4,6,121,2,3,4,6,12 の 66 個です。

  • 11 の約数の和 : 1=11=1
  • 22 の約数の和 : 1+2=31+2=3
  • 33 の約数の和 : 1+3=41+3=4
  • 44 の約数の和 : 1+2+4=71+2+4=7
  • 66 の約数の和 : 1+2+3+6=121+2+3+6=12
  • 1212 の約数の和 : 1+2+3+4+6+12=281+2+3+4+6+12=28

よって、出力すべき値は、1+3+4+7+12+28=551+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もしくは右上の雲マークをクリックしてアカウントを作成してください。