算法刷题【洛谷P1593】因子和(附等比数列求和公式推导)

异想之旅:本人原创博客完全手敲,绝对非搬运,全网不可能有重复;本人无团队,仅为技术爱好者进行分享,所有内容不牵扯广告。本人所有文章仅在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 因子和] {快速幂+费马小定理求逆元+求解质因子} 奋斗的珂珂~ - 代码先锋网


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


等比数列定义很简单,设有数列 [ 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​

(参考资料:等比数列公式及推导_高三网


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

算法刷题【洛谷P1593】因子和(附等比数列求和公式推导)

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

上一篇:【100个 Unity小知识点】☀️ | Unity 中的原始预制体 和 预制体变体 的区别和作用


下一篇:正交投影、格拉姆施密特正交