异想之旅：本人原创博客完全手敲，绝对非搬运，全网不可能有重复；本人无团队，仅为技术爱好者进行分享，所有内容不牵扯广告。本人所有文章仅在CSDN和个人博客（一定是异想之旅域名）发布，除此之外全部是盗文！

---

洛谷 P1593 因子和

题目描述

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

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

输入格式

仅一行，为两个整数 $a$ 和 $b$。

输出格式

输出一行一个整数表示答案对 $9901$ 取模的结果。

输入输出样例

In 1：

2 3

Out 1：

15

数据范围

对于全部的测试点，保证 $1\le a\le 5\times 10^7$，$0\le b\le 5\times 10^7$。

题解

为了完成洛谷P1593这道题也是拼了……用到了三个不会的知识：因子和公式和等比数列求和公式和费马小定理求分数

这里另摆一份很好的题解：洛谷 [P1593 因子和] {快速幂+费马小定理求逆元+求解质因子} 奋斗的珂珂~ - 代码先锋网

---

先摆出因子和公式的参考资料：

• 数论-约数和公式_Ice_teapoy的博客-CSDN博客_约数和公式
• 约数和公式 及其 证明 。。小学奥数啊 摔~_用心一也-CSDN博客_约数个数公式

---

等比数列定义很简单，设有数列 $[a_1,a_2,...,a_n]$ ，存在一个定值 $q$ 使得任意 $1\le i\le n-1$ 都有 $a_{i+1}=a_i\times q$ 。由此定义可知 $a_n=a_1\times q^{n-1}$ 。

这个数列的求和公式为 $S_n=a_1+a_2+...+a_n=a_1\times \frac{1-q^n}{1-q}$ ，下面我们来证明这个公式：

$\because q{S}_n=q{a}_1+q{a}_2+...+q{a}_n=a_2+a_3+...+a_{n+1}$

$\therefore S_n-q{S}_n=(1-q)S_n=a_1-a_{n+1}=a_1-(a_1\ast q^n)=a_1(1-q^n)$

$\therefore S_n=a_1\frac{1-q^n}{1-q}$

（参考资料：等比数列公式及推导_高三网）

---

费马小定理求分数快速幂的公式及证明：

（来源：分数取模(费马小定理)_give it a try-CSDN博客_分数取模运算）