信奥题库（OI题库）8月月赛T1题解 幂次数

0.前置知识
分解质因数 快速幂(不必要)
1.思路
首先，我们知道一个正整数(设它为 /(a/) )一定能分解成这样的形式：

/[a= /prod_{i/in N^*} p_i^{c_i} /]

其中， /(p/) 为质数序列。
就是分解质因数。

幂次数可以表示为 /(a^b/)(其中 /(a/) 为质数， /(b/) 为自然数)。如果 /(a^b/) 整除正整数 /(x/) ，并且 /(a^{b+1}/) 不整除 /(x/) ，那么我们称 /(a^b/) 为正整数 /(x/) 的幂次数。 ——摘自题目

结合上面的“ /(p_i^{c_i}/) ”，是不是发现了什么？没错， 幂次数一定等于 /(p_i^{c_i}/) ！至于为什么，因为 /(a/) 一定是一个质数(也就代表了不可能有因数)，而且 /(p_i^{c_i}/) 一定能整除 /(x/) ，/(p_i^{c_{i-1}}/) 、 /(p_i^{c_{i-2}}/) 这些都存在 /(a^{b+1}/) 能整除 /(x/)

信奥题库（OI题库）8月月赛T1题解 幂次数最先出现在Python成神之路。