时间与空间

题目描述

引言：古有二尊并存，其一看时光流转，其一看地阔天宽。为求未来之后的未来，欲探天地尽头的天地。二尊各行其道，与神奥大尊相随常伴。——《古老诗文1》

呱呱泡蛙想要去古神奥。它打开阿尔宙斯手机，收到有关时空旅行的信息：

主定理（Master Theorem）是算法分析的第一个定理，用于研究分治类问题的时间复杂度和空间复杂度。这个定理的名字叫“主定理”，听起来很古怪。

假设一个规模为 $n$ 的大问题 $T(n)$ 可以拆成 $a$ 个规模为 $\frac{n}{b}$ 的小问题，外加一个只和 $n$ 相关的函数项问题 $f(n)$ ，$a\ge 1$ 和 $b>1$ 都是常数，形如这个表达式：

$$ T(n)=aT(\frac{n}{b})+f(n) $$

此时就可以根据函数项问题 $f(n)$ 的阶来估计大问题 $T(n)$ 的阶数。

描述函数的阶，使用大写Theta符号，即 $\Theta(f(n))$ 。

情形1：如果 $f(n)$ 的阶很小。对照的参照物是幂函数 $n^{\log_b a}$ 。如果有：

$$ \Theta(f(n))<n^{\log_b a} $$

函数 $f(n)$ 比这个幂函数严格小，此时函数 $f(n)$ 这项可以直接省略不计。此时问题 $T(n)$ 的复杂度：

$$ \Theta(T(n))=n^{\log_b a} $$

问题 $T(n)$ 的复杂度直接就是该幂函数。

情形2：如果 $f(n)$ 的阶中等。对照的参照物是幂函数 $n^{\log_b a}$ 乘上若干个对数函数 $\log n$ ，这个“若干个”可以为零个。如果有：

$$ \Theta(f(n))=n^{\log_b a}\log^k n\quad k\ge 0 $$

此时问题 $T(n)$ 的复杂度：

$$ \Theta(T(n))=n^{\log_b a}\log^{k+1} n $$

会比之前的对数个数增加一个。

情形3：如果 $f(n)$ 的阶很大。此时函数 $f(n)$ 必须要打破上述表达式的限制。不仅要有：

$$ \Theta(f(n))>n^{\log_b a} $$

还要对于某个常数 $c>1$ 和所有充分大的 $n$ 有：

$$ cf(n)\ge af(\frac{n}{b}) $$

此时函数 $T(n)$ 会受到函数 $f(n)$ 的连累，也脱离表达式的限制，有：

$$ \Theta(T(n))=\Theta(f(n)) $$

鉴于本题中可能出现的阶一律写成如下形式：

n^xlog^y(n)，x和y为非负的整数或小数，例如n^2log^0(n) 

对于算法而言，超出多项式的复杂度（诸如指数和阶乘）是实际应用不会涉足的领域，因此在此处不考虑。本题也不会出现其他复杂的函数，所以情形3的条件，直接判断是否高阶即可。

输入

多行输入，每行的结构是：小数 $a\ge 1$ 、空格、小数 $b>1$ 、空格、函数 $f(n)$ 的阶。

输入的函数 $f(n)$ 的阶是两个非负浮点数 x 和 y ，表示 $n^x\log^y(n)$。

输出

对于每行数据，输出一行，为函数T的阶。

输出格式为n^xlog^y(n)，两个非负浮点数 x 和 y 保留3位小数。

输出数据的某部分如果为0或1，则简化该部分。如果为0则不输出，都为0则输出1。如果为1则输出不带相应上标。

输入样例

2 2 0 1

输出样例

n

其他

大O记号和小o记号，是函数的阶的更加规范的描述。在数据结构和算法中的大O记号是“小于等于”的含义，在数学分析中的小o记号是“小于”的含义。它们原本是希腊字母Omicron，由于字形相同，也可以理解为英文字母大O和小o。

英文-micro-和英文-mega-表示10的负六次方（百万分之一）和六次方（百万），也表示“小”和“大”。小和大也是希腊字母Omicron和Omega常表示的含义。

后记：时间是不停歇的奔流。是过去，是未来，是现在……空间是无止尽的延展。而心灵，亦是空间……——《古老诗文15》

Author：买到传说阿尔宙斯的呱呱泡蛙