← 返回题目列表

Codeforces · 233/B

B. 非平方方程

中文机器翻译题面 查看原题

让我们考虑一下方程:

x2 + s(x)·x - n = 0,

其中x、n是正整数,s(x)是函数,等于十进制数字x的各位数字之和。

给定一个整数n,找到方程x的最小正整数根,否则确定不存在这样的根。

输入

单行包含整数 n (1 ≤ n ≤ 1018) — 方程参数。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

输出

如果方程没有整数正根,则打印 -1。否则,打印语句中给出的方程成立的最小整数 x (x > 0)。

示例

输入 #1

2

输出 #1

1

输入 #2

110

输出 #2

10

输入 #3

4

输出 #3

-1

注意

在第一个测试用例中,x = 1 是最小根。由于 s(1) = 1 且 12 + 1·1 - 2 = 0。

在第二个测试用例中,x = 10 是最小根。由于 s(10) = 1 + 0 = 1 且 102 + 1·10 - 110 = 0。

在第三个测试用例中,方程没有根。