問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 167
作問者 : startcppstartcpp / テスター : はむこはむこ
3 ProblemId : 1709 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-05-17 12:29:19

問題文

$xy$平面上に, 原点$O$を中心とする半径$\sqrt R$の円があるとき, 円周上にある格子点の個数を$f(R)$とおく。
格子点は, $x$座標$y$座標がともに整数の点である。
たとえば, $f(1) = 4, f(5) = 8, f(25) = 12$である。

$R$の最小値$X$, 最大値$Y$が与えられるので、$max(f(X), f(X+1), …, f(Y))$を求めよ。ただし, $X=Y$のときは$f(X)$を求めよ。

入力

X Y

$X$, $Y$は整数である.
$1 \le X \le Y \le 10^7$

出力

$f(X)$~$f(Y)$の最大値を出力してください。ただし, f(整数)のみ考えます。
最後に改行してください。

サンプル

サンプル1
入力
25 25
出力
12

$25$の平方根のうち正の方は$5$です。
半径$5$の円(原点中心)の円周上には, $12$個の格子点があります。
したがって、$f(25) = 12$となります。

サンプル2
入力
1 50000
出力
64

$f(1)~f(50000)$までの最大値は, $f(27625) = 64$です。

サンプル2
入力
33455 37510
出力
48

$f(33455)~f(37510)$までの最大値は, $f(34450) = 48$です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。