ARC125 B - Squares (500)
作る平方数を
$ a^2 (a \le \sqrt{n})
とすると、
$ x^2-y=a^2
なので、
$ (x+a)(x-a)=y
$ x-a=t
とすると、
$ x+a=x+x-t=2x-t
取れる値の偶奇が決まっていることが分かる
$ 2x-t
の上限は
$ min(2n-t,\lfloor n/t \rfloor)
これを
$ t=1,2,... \cdots, \sqrt{n}
まで行えば良い
全体で
$ \mathcal{O}(\sqrt{n})
問題:
https://atcoder.jp/contests/arc125/tasks/arc125_b
提出:
https://atcoder.jp/contests/arc125/submissions/25276582
#ARC125
#500pt
#B
#ARC
#AtCoder
#因数分解