luogu#P11496. [ROIR 2019 Day 1] 完全平方

[ROIR 2019 Day 1] 完全平方

题目背景

翻译自 ROIR 2019 D1T2

题目描述

我们知道序列 0,0+1,0+1+3,0+1+3+5,,0+1+3++(2i1),0,0+1,0+1+3,0+1+3+5,\dots,0+1+3+\dots+(2i-1),\dots 的第 ii 项是 i2i^2,即,这个序列里的数全部都是完全平方数。

现在我们不让这个序列从 00 开始,而是从 kk 开始:k,k+1,k+1+3,k+1+3+5,,k+1+3++(2i1),k,k+1,k+1+3,k+1+3+5,\dots,k+1+3+\dots+(2i-1),\dots

你需要找到这个序列中最小的完全平方数,并输出它的算术平方根。

输入格式

输入一个整数 kk

输出格式

输出序列中最小的完全平方数的算术平方根,如果没有,输出 none

0
0
-5
2
2
none

提示

样例解释:

  • 样例 11 中的序列即为题目中提到的完全平方数序列,其中最小的数是 000=0\sqrt0=0
  • 样例 22 中的序列为 5,4,1,4,11,20,-5,-4,-1,4,11,20,\dots,其中最小的完全平方数是 444=2\sqrt4=2
  • 样例 33 中的序列为 2,3,6,11,18,2,3,6,11,18,\dots,可以证明其中不存在完全平方数。

数据范围:

数据中 Subtask 0 为样例。

子任务 分值 特殊性质
11 77 0k10000\le k\le1000
22 1010 0k1050 \leq k \leq 10^5
33 2727 0k10120 \leq k \leq 10^{12}
44 77 1000k1000-1000 \leq k \leq 1000
55 1010 105k105-10^5 \leq k \leq 10^5
66 3939 1012k1012-10^{12} \leq k \leq 10^{12}