P1593 因子和

题意简述

输入两个整数 $a$ 和 $b$，求 $a^b$ 的因子和。

由于结果太大，只要输出它对 $9901$ 取模的结果。

保证 $1 \leq a \leq 5 \times 10^7$，$0 \leq b \leq 5 \times 10^7$。

题目分析

本题考察基础数论的综合运用。

按照题意进行操作即可，注意细节：

1. 质因数分解

2. 求因子和

3. 求逆元

   因为本题在使用等比数列求和公式时需要除法，所以需要求逆元。

   还要注意本题求解逆元的模数较小，可能存在数据不存在逆元的情况。即存在：

   $$a \equiv 1 \pmod {\text{MOD}}$$

   此时 $a$ 不存在模 $\text{MOD} = 9901$ 意义下的逆元。

   观察可知，$9901$ 是质数，使用费马小定理求解逆元即可。

Code