I - 互いに素でないペアを持つ N の約数の集合の個数を求めてください。

Contest Duration: 2019-07-28 13:00:00+0900 - 2019-07-28 18:00:00+0900 (local time) (300 minutes) Back to Home

I - 互いに素でないペアを持つ N の約数の集合の個数を求めてください。 Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 700 点

互いに素でないペアを持つ N の約数の集合の個数を求めてください。

N は M 個の自然数 A_1A_2...A_{M-1}A_M の積であり、以下の形式で標準入力から与えられます。

M
A_1 A_2 ... A_{M-1} A_M

条件を満たす集合の個数を 10^9+7 で割ったあまりを出力してください。

1
6

N = 6 のとき、(2, 6), (3, 6), (2, 3, 6), (1, 2, 6), (1, 3, 6), (1, 2, 3, 6) の 6 つの集合が条件を満たします。

2
2 3

N = 2 \times 3 = 6であり、入出力例 1 と等しい問題です。

10
16808 282475250 622650074 984943659 144108931 470211273 101027545 457850879 458777924 7237710

820588505

10^9+7 で割った余りを求めることに注意してください。