AdditionalFile4900.zip

#4900. 「POI2015 R1」平方和 Squares

标签: 传统 | 时间限制: 100 ms | 内存限制: 64 MiB |

题目描述

题目译自 XXII Olimpiada Informatyczna — I etap Kwadraty

在这道题中，我们研究正整数如何分解为不同正整数平方之和（简称分解）。例如，$30$ 有两种分解方式：$1^{2}+2^{2}+5^{2}=1^{2}+2^{2}+3^{2}+4^{2}=30$，而 $8$ 没有任何分解。

我们关心的问题是：对于给定的数 $n$，其分解中最大数是多少？换句话说，我们要找出 $k(n)$，即所有分解中最大数的最小值。为简化起见，若 $n$ 无法分解，则定义 $k(n)=\infty$。例如，$k(1)=1, k(8)=\infty, k(30)=4, k(378)=12, k(380)=10$。

我们称一个数 $x$ 为超大数，若存在 $y > x$ 使得 $k(y) < k(x)$。从上述例子可知，$378$ 是超大数。

对于给定的 $n$，请你计算 $k(n)$ 以及 $1$ 到 $n$ 范围内超大数的数量。

输入格式

输入只有一行，包含一个正整数 $n$ $(1 \leq n \leq 10^{18})$。

输出格式

输出一行，包含两个整数：第一个是 $k(n)$，第二个是 $1$ 到 $n$ 范围内超大数的数量。若 $k(n)=\infty$，第一个数输出 -。

样例 1

输入

30

输出

4 15

样例 2

输入

8

输出

- 5

附加样例

1. $n=1000$，小型样例；
2. $n=1000000$，中等规模样例；
3. $n=50000000$，大型样例。

数据范围与提示

对于 $45\%$ 的数据，$n \leq 50000000$。
对于其中 $30\%$ 的数据，$n \leq 1000000$。
对于其中 $20\%$ 的数据，$n \leq 1000$。