hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング 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… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2019%2F01%2F12%2F165658" title="円周上の格子点の数え上げ [yukicoder No.781] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-01-12 16:56:58 rich https://blog.hamayanhamayan.com/entry/2019/01/12/165658 1.0 100%