atcoder.jp 問題 長さNの非負整数列Aが与えられるよ 以下の条件を満たす整数組$(i,j)$は何個ある? $1 \leq i < j \leq N$ $A_i \times A_j$は平方数 成約 $2 \leq N \leq 2 \times 10^{5}$ $0 \leq A_{i} \leq 2 \times 10^{5}$ 思考 iとjを全部見ていくのはまぁ間に合いません… オチとしては、iを集計しつつjを1つずつ見ていく、みたいな話 平方数の判定 $n$を素因数分解して、$a^{i} \times b^{j} \times c^{k} ...$の形にする 指数?i,j,kを…