ABC 401-500/ABC439C - 2026 - 競技プログラミング用 知識集積所

---

問題

ABC439C

必要知識

B以下レベルの内容は省略

• 特になし

考え方

1つ1つの値について、それが何パターンの(x,y)で作れるかカウントするとTLE。
しかし、どうせN以下の全ての値に対してチェックするなら、視点を逆にすればよい。
すなわち、0<x<yかつy*y<=nの範囲で全てのx^2+y^2を計算し、それぞれ「その結果が1回作れた」を記録してやればよい。

0からNまでに対応するN+1要素のvector上に記録して、全て終わったら中身が1である要素がある位置を全て出力すればよい。

この方針は、用意するvectorの長さはN+1で、二重ループ※も合計でおよそN回程度なので、Nが10^7程度であれば十分間に合う。

解答例

解答例

注意点

別解

set※などを2つ使う方法もある。

1回以上出現した数と、2回以上出現した数とを、それぞれset※などで管理する方法もある。
vectorよりも効率は悪いが、今回の制約なら間に合う。
解答例