P6391 - [文科综合]历史

题目

P6391[文科综合]历史

限制 : 时间限制 : 10000 MS 空间限制 : 524288 KB

评测说明 : 1s,512MB

问题描述

一个民族的强弱随着时间的推移不断发生变化。在和平年代，人们发展经济，重视教育，带动文化产业发展，日益富强；在战争年代，经济停滞不前，教育被忽视，社会生产力和劳动力大打折扣。

nodgd用一个正整数$a_i$表示某民族在第$i$年的强度。如果第$i$年的民族强度$a_i$是完全平方数，则这一年会发生战争，导致第$i+1$年的民族强度$a_{i+1}=\sqrt{a_i}$；否则第$i$年和平发展，第$i+1$年的民族强度$a_{i+1}=a_i+k$，其中$k$是一个正整数。

假如一个民族现在（第$0$年）的强度是$a_0$，nodgd想知道以下两个问题的答案：

这个民族能够达到的最大强度是多少？如果没有上限则输出-1。
至少经过多少年后，这个民族的强度首次等于$m$？如果无法等于$m$则输出-1。

输入格式

输入一行三个正整数$a_0,k,m$，表示现在的民族强度、和平年代的发展速度、询问的民族强度。

输出格式

输出两行，每行一个整数，依次是两个问题的答案。

样例输入 1

12 3 9

样例输出 1

36
10

样例输入 2

125 4 1

样例输出 2

-1
-1

样例输入 3

5054693 49 1239658

样例输出 3

-1
25832

样例输入 4

5961245 47 188

样例输出 4

5973136
393

提示

样例说明1

以下是前若干年的民族强度变化情况：

\[ \begin{align} a_0&=12\\ a_1&=15\\ &\dots\\ a_8&=36\\ a_9&=6\\ a_{10}&=9\\ a_{11}&=3\\ a_{12}&=6\\ &\dots \end{align} \]

此后一直在$3,6,9$这三个数中循环，所以最大强度为$36$，在第$10$年首次强度等于$9$。

样例说明2

以下是前若干年的民族强度变化情况：

\[ \begin{align} a_0&=125\\ a_1&=129\\ &\dots\\ a_{11}&=169\\ a_{12}&=13\\ a_{13}&=17\\ a_{14}&=21\\ a_{15}&=25\\ a_{16}&=5\\ a_{17}&=9\\ a_{18}&=3\\ a_{19}&=7\\ a_{20}&=11\\ &\dots \end{align} \]

从$a_{18}=3$开始每年都是和平发展，随着时间推移民族强度趋于无穷大，而且没有任何一年的民族强度等于$1$。

数据规模与约定

对于10%的数据，$k=1$；

对于另外10%的数据，$k=2$；

对于另外10%的数据，$k=3$；

对于前40%的数据，$k\leq 50,\quad a_0,m\leq 10^7$；

对于前70%的数据，$k\leq 10^5$；

对于100%的数据，$2\leq k\leq 10^7,\quad a_0,m\leq10^{18}$。