UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3748. [POI2015]Kwadraty

统计 下载数据

Description

考虑将正整数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中有几个“超重”的数。

Input

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

Output

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

Sample Input

样例输入1:
30


样例输入2:
8

Sample Output

样例输出1:
4 15

样例输出2:
- 5

Hint

Source

鸣谢Jcvb