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

洛谷 P1593 因子和

题目描述

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

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

输入格式

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

输出格式

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

输入输出样例

In 1：

2 3

Out 1：

15

数据范围

对于全部的测试点，保证 1 ≤ a ≤ 5 × 1 0 7 1 \leq a \leq 5 \times 10^7 1≤a≤5×107， 0 ≤ b ≤ 5 × 1 0 7 0 \leq b \leq 5 \times 10^7 0≤b≤5×107。

题解

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

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

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

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

等比数列定义很简单，设有数列 [ a 1 , a 2 , . . . , a n ] [a_1, a_2,...,a_n] [a1​,a2​,...,an​] ，存在一个定值 q q q 使得任意 1 ≤ i ≤ n − 1 1 ≤ i ≤ n-1 1≤i≤n−1 都有 a i + 1 = a i × q a_{i+1} = a_i \times q ai+1​=ai​×q 。由此定义可知 a n = a 1 × q n − 1 a_n = a_1 \times q^{n-1} an​=a1​×qn−1 。

这个数列的求和公式为 S n = a 1 + a 2 + . . . + a n = a 1 × 1 − q n 1 − q S_n = a_1 + a_2 + ... + a_n = a_1 \times \frac{1-q^n}{1-q} Sn​=a1​+a2​+...+an​=a1​×1−q1−qn​ ，下面我们来证明这个公式：

∵ q S n = q a 1 + q a 2 + . . . + q a n = a 2 + a 3 + . . . + a n + 1 ∵ qS_n = qa_1 + qa_2 + ... + qa_n = a_2 + a_3 + ... + a_{n+1} ∵qSn​=qa1​+qa2​+...+qan​=a2​+a3​+...+an+1​

∴ S n − q S n = ( 1 − q ) S n = a 1 − a n + 1 = a 1 − ( a 1 ∗ q n ) = a 1 ( 1 − q n ) ∴ S_n - qS_n = (1-q) S_n = a_1 - a_{n+1} = a_1 - (a_1 * q^n) = a_1(1-q^n) ∴Sn​−qSn​=(1−q)Sn​=a1​−an+1​=a1​−(a1​∗qn)=a1​(1−qn)

∴ S n = a 1 1 − q n 1 − q ∴ S_n = a_1 \frac{1-q^n}{1-q} ∴Sn​=a1​1−q1−qn​

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

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

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