2763: T2 徐老师的正方形拼图
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：10
解决：1
题目描述
徐老师有大大小小的正方形木板许许多多块，这些正方形木板的边长至少为$1$(当然也可能更大)，且都是整数。徐老师想选择其中$n$块个正方形木板拼成（注意是拼成，不是叠加或者挖洞嵌进去）一个大的正方形。请帮徐老师求这个大正方形**边长**的最小值。
输入
本题每个测试点包含多组（$\le10^6$）数据。
每行一个不超过（$\le10^6$）的正整数n，表示使用的正方形数量。
每行一个不超过（$\le10^6$）的正整数n，表示使用的正方形数量。
输出
每行输出一个拼接后的大正方形**边长**的最小值（无解输出$-1$）。
样例输入 复制
1
2
12样例输出 复制
1
-1
6提示
## 数据范围
| 测试点 | 木块数量 $n$ | 特殊性质 |
| :----: | :----------: | :------: |
| 1~5 | $\le25$ | 无 |
| 6~10 | $\le50$ | 无 |
| 11~20 | $\le100$ | 无 |
| 20~25 | $\le10^6$ | 无 |
题解：
比如$n=7$输出$4 (sqrt(3*4+4*1))$
如果$n$是完全平方数，则输出$sqrt(n)$。
否则用边长更大的正方形替代多个边长为1的正方形，
即等价于求方程$m * m - n - 3a - 8b - 15c - 24d - .... = 0 $的最小正整数解$m$。
由于$3a + 8b = k $当$ k > 13$时， 一定有非负整数解。
所以等价于求方程$ m * m - n - 3a - 8b = 0 $的最小正整数解$m$。
令$m = ceil(sqrt(n+3)) $或者$ ceil(sqrt(n+3)) + 1 $或者 $ceil(sqrt(n+3)) + 2$ 且$m <= ceil(sqrt(n)) + 2$
求方程$m*m - n - 3a - 8b = 0 $的最小正整数解$m$，其中$n、a$和$b $都是非负整数。
且$ a + b$必须$<= m/2 * m/2；$
$b必须 <= m/3 * m/3；$
如果$a*b$非$0$，则$m > 4$。
| 测试点 | 木块数量 $n$ | 特殊性质 |
| :----: | :----------: | :------: |
| 1~5 | $\le25$ | 无 |
| 6~10 | $\le50$ | 无 |
| 11~20 | $\le100$ | 无 |
| 20~25 | $\le10^6$ | 无 |
题解：
比如$n=7$输出$4 (sqrt(3*4+4*1))$
如果$n$是完全平方数，则输出$sqrt(n)$。
否则用边长更大的正方形替代多个边长为1的正方形，
即等价于求方程$m * m - n - 3a - 8b - 15c - 24d - .... = 0 $的最小正整数解$m$。
由于$3a + 8b = k $当$ k > 13$时， 一定有非负整数解。
所以等价于求方程$ m * m - n - 3a - 8b = 0 $的最小正整数解$m$。
令$m = ceil(sqrt(n+3)) $或者$ ceil(sqrt(n+3)) + 1 $或者 $ceil(sqrt(n+3)) + 2$ 且$m <= ceil(sqrt(n)) + 2$
求方程$m*m - n - 3a - 8b = 0 $的最小正整数解$m$，其中$n、a$和$b $都是非负整数。
且$ a + b$必须$<= m/2 * m/2；$
$b必须 <= m/3 * m/3；$
如果$a*b$非$0$，则$m > 4$。