BigFatInteger

作者 : 翁伊嘉

关键词 : 简单数论(?) 快速幂(?)

题目简述

输入两个整数$A, B$. $A, B \le 10^6$.

你有一个数字$d$,$d$初始为$1$。每次你可以对$d$进行以下两种操作之一：

• 给$d$乘上一个任意的质数$p$
• 给$d$乘上它目前的一个因子

输出将$d$变成$A^B$所需要的最小操作次数。

分析

两种操作都只涉及乘法，考虑把$A^B$分解质因数，问题相当于是采用最少的操作，让每个质因数$p_i$都在$d$中出现指定的$c_i$次。

假设$A^B$中只包含一种质因子$p$，且$A^B = p ^ c$. 最优策略一定是先采取一次第一种操作，使$d = p$,然后用类似快速幂的办法，用$\lceil \log_2{c} \rceil$次操作把$d$变成$p^c$

有$cnt$个质因子的情况也一样，首先采取$cnt$次第一种操作使$d = \prod_{i = 1}^{cnt} p_i$,接着进行第二种操作。每个第二种操作中，各个质因子的增加情况是互相独立的，因此第二种操作的最少次数由增加到$p_i^{c_i}$所需要操作次数最多的的质因子$p_i$决定。

算法

将$A$分解质因数，每种质因子的出现次数再乘上$B$，得到$A^B$中每个质因子$p_i$出现的次数$c_i$.

根据之前的分析，$Ans = cnt + \max_{i = 1}^{cnt} \{\lceil \log_2{c_i} \rceil\}$

时间复杂度$O(\sqrt{A})$.空间复杂度$O(1)$