ABC254 D - Together Square (400)
$ n
以下の平方数全てを事前に求めておく
$ 1 \le i \le n
について以下を行う
平方数で割りきれるなら割っておく
これを
$ v
とする
$ j
も同様に割り切った後は
$ v
である必要がある
そのような
$ j
の数は
$ \frac{N}{v}
以下の平方数の個数なので二分探索で求まる
それぞれで二分探索を行うので
$ \mathcal{O}(N \log N)
問題:
https://atcoder.jp/contests/abc254/tasks/abc254_d
提出:
https://atcoder.jp/contests/abc254/submissions/32214393
#ABC254
#400pt
#D
#ABC
#AtCoder
#O(NlogN)