Power Divisors

2 secs 1024 MB
sgsw

問題文


(難易度目安:点)

長さの自然数のみから構成される数列に対し、以下を満たす自然数のペアの個数はいくつ存在するか答えてください。

の約数の個数はの冪乗である。

制約


・入力はすべて整数

入力


入力は以下の形式で与えられます。

N 
A_1 A_2 ... A_N

出力


ペアの個数を1行で出力してください。

最後に改行してください。

サンプル


入力1
3
2 3 4
出力1
2

この時、ペアは全てで通り考えられ、それぞれ得られる数はとなります。

このそれぞれに対して約数の個数を数えるとであり、の冪乗に等しいものはつ存在します。

したがって、を出力します。

入力2
4
1 1 2 2
出力2
5

この時として考えられる値は通りであり、それぞれの約数の個数はとなります。

このうち、の冪乗に等しいものはつ存在します。

入力3
20
452902405 396883670 481861767 674061260 805187376 974697172 198697835 259654289 717370511 155641344 525659558 869302670 185490765 647522638 831270876 761020820 560278586 960923514 270814672 563095766
出力3
59

Submit


Go (1.14)