Problem Detail - Kwadraty

ID: 2305

Type: RemoteJudge

1000ms

256MiB

Difficulty: (None)

Uploaded By:

No submission language available for this problem.

题目描述

考虑将正整数n拆分成几个不同的平方数之和，比如30=1^2 + 2^2 + 5^2=1^2 + 2^2 + 3^2 + 4^2，而8不存在这样的拆分。

用k(n)表示n的拆分中，最大的底数最小可能是多少。如果n不存在这样的拆分，则令k(n)=∞。例如，k(1)=1,k(8)=∞,k(378)=12,k(380)=10。

定义一个数x被称为“超重”的，当且仅当存在y>x，使得k(y)<k(x)。从上面的例子可知，378是一个“超重”的数。

给定n，你需要：

(1)求出k(n)

(2)求出1~n中有几个“超重”的数。

输入仅一行，包含一个正整数n(1<=n<=10^18)。

输出一行包含两个整数，分别为对上述两个问题的答案。如果k(n)=∞，则输出一个减号'-'代替。

样例输入1： 30   样例输入2： 8

样例输出1： 4 15  样例输出2： - 5