B - ニワンゴくんの約数
解説
/
実行時間制限: 2.525 sec / メモリ制限: 246 MB
配点 : 1100 点
問題文
ニワンゴくんは、正の整数からなる数列 x_1,\ x_2,\ ...,\ x_N を持っています。次の Q 個のクエリに順に答えてください。
- クエリ: 1 ≦ l_i ≦ r_i ≦ N が与えられるので、x_{l_i},\ x_{l_i+1},\ ...,\ x_{r_i} の積 x_{l_i}x_{l_i+1}...x_{r_i} の約数の個数を 10^9 + 7 で割ったあまりを求めよ。
制約
- 1 ≦ N, Q ≦ 10^5
- 1 ≦ x_i ≦ 10^5 (1 ≦ i ≦ N)
- 1 ≦ l_i ≦ r_i ≦ N (1 ≦ i ≦ Q)
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N Q x_1 : x_N l_1 r_1 : l_Q r_Q
出力
クエリ毎に、整数 x_{l_i}x_{l_i+1}...x_{r_i} の約数の個数を 10^9 + 7 で割ったあまりを一行に出力せよ。
入力例 1
6 5 2 6 5 18 4 15 1 6 2 4 1 3 2 6 4 4
出力例 1
90 24 12 75 6
最初のクエリにおいて、x_1x_2x_3x_4x_5x_6=64800 の約数の個数は 90 個なので、90 を出力します。
入力例 2
10 6 3003 57600 4320 100000 3456 2197 2187 65536 90090 8128 1 10 2 5 3 7 1 4 3 6 7 10
出力例 2
1005480 2106 7056 9576 3528 7680