円周上の格子点の数え上げ [yukicoder No.781]

https://yukicoder.me/problems/no/781

解説

https://yukicoder.me/submissions/310016

原点Oを中心とする、半径root(R)の円の式は x^2+y^2=Rとなる。
よって、格子点は x,yが整数でx^2+y^2=Rを満たす頂点である。
Rの最大値が10^7であるが、このときのx,yの範囲は10^7＜4000^2なので、[-4000,4000]くらいで足りる。
つまり、候補となる格子点は全列挙できるということである。
そのため、全列挙して、R毎に数えたあと、[X,Y]の範囲で最大値を求めればいい。
cnt[r] := x^2+y^2=rを満たす格子点の数

int X, Y;
int cnt[10101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> Y;
    rep(x, -4000, 4000) rep(y, -4000, 4000) if (x*x + y * y <= Y) cnt[x * x + y * y]++;
    int ans = 0;
    rep(r, X, Y + 1) chmax(ans, cnt[r]);
    cout << ans << endl;
}