poj1845 sumdiv 题解
Emmm...并非题解
其实是边想边写现编的
先审题：
考虑两个自然数 A 和 B。令 S 为$ A^B $的所有自然因子之和。确定 S 除以 9901 的余数.
eg. \(2^3 = 8\)。 8 的自然因子是：1、2、4、8。它们的和是 15。 15 除以 9901 的余数是 15（输出值）。
啊，好简洁的题面像我的大脑一样！
可以肯定的，\(A\)的因子一定是\(A^B\)的因子依旧废话
而且我们会发现，\(A^B\)的质因子一定与A的质因子完全相同。
很简单吧 谁问你了
思路
这时候，可以想到：(敲黑板，这是重点/)
对 A 进行 唯一分解
\[\large A = \prod _{i=1}^{k}{(P_i^{e_i})}
\] 还是拆开好看：
\[\large A= P_1^{e_1} \times P_2^{e_2} \times ... \times P_k^{e_k}
\] ——其中\(P_i\) 表示A的质因子，\(e_i\)表示该质因子的次数。
那\(A^B\)就是给每个\(e_i\)乘上一个B就好了。
应该没人不知道这个吧
很显然地，A的 因子 就是一个x，使得：
\[\large x= P_1^{v_1} \times P_2^{v_2} \times ... \times P_k^{v_k}
\] 其中\(v_i < e_i\).
Emmm...还是不好求嘞...
求解
题目要求我们求所有x的和，
每个\(P_i\)会被算:
\[\tag {1} 1+P_i^1 + P_i^2 + P_i^3 + ... + P_i^{e_i}
\] 引入一个另外的一次质因子\(P_j\), 与上面组合，答案就是：
\[\tag {2} 1 \times P_j + P_i^1 \times P_j + P_i^2 \times P_j + ...
\] 可以发现，\((2)=(1)\times P_j\).
那么多次的\(P_j\)就是：
\[(1) + (1) \times P_j^1 + (1) \times P_j^2 +...(1) \times P_j^{e_j}
\] 嘿，您猜怎么着， 咱把这 (1) 一提:
\[(1) \times (1+P_j^1+P_j^2+P_j^3+...+P_j^{e_j})
\] 诶呦喂，瞧瞧，我是不是在哪遇见过您？awa
这就是变了个样的 (1) 啊!
噫嘘兮，情乎喜哉！数论之易，易于切水题。
很好，我们只要求每个\(P_i\)所对应的(i),对其求积就可以了。
应该吧QAQ
拓展
没想到吧，这篇题解还有拓展awa
注意：
\[(I) = 1+P_i^1 + P_i^2 + P_i^3 + ... + P_i^{e_i}
\]
有没有发现什么端倪?
oi,这不是个等比数列吗
这里是错解，之前没看就发出来也许干扰了大家的思路，万分抱歉orz
\[\tag{1} (I) = 1+P_i^1 + P_i^2 + P_i^3 + ... + P_i^{e_i}
\] \[\tag{2} P_i \times (I) = P_i^1 + P_i^2 + P_i^3 + ... + P_i^{e_i}+P_i^{e_i+1}
\] (2)-(1),得
\[(P_i-1) \times (I) =P_i^{e_i+1}-1
\] 那么有
\[(I)=\frac{P_i^{e_i+1}-1}{P_i-1}
\] ...太丑了吧
虽然丑，但它好求啊，这不比一个一个枚举快多了qwq
不过...这个式子必须用 乘法逆元 二次化简再取模，不然求得解是错的 (原因：模运算不具有同除性)
我这个蒟蒻没学过就不在这里做洋相了
所以这是一个错解！QAQ
下面是正解
既然普通的等比数列求法不成立， 那么我们就试一些 不同寻常 的解法
观察等比数列结构：
\(\large S=1+P_i^1+P_i^2+P_i^3+...P_i^{e_i}\)
其实能用分治！
当\(e_i\)是奇数时，以5为例：
\(\large S =1+P_i^1+P_i^2+P_i^3+P_i^4+P_i^5\)
\(\large \quad = (1+P_i^1+P_i^2) +P_i^3 \times (1+P_i^1+P_i^2)\)
\(\large \quad = (1+P_i^3)\times (1+P_i^1+P_i^2)\)
\(\large \quad = (1+P_i^{\frac{e_i}{2}+1})\times (1+P_i^1+...+P_i^{\frac{e_i}{2}})\)
当\(e_i\)是偶数时，以4为例：
\(\large S =1+P_i^1+P_i^2+P_i^3+P_i^4\)
\(\large \quad = (1+P_i^1)+P_i^2 +P_i^3 \times (1+P_i^1)\)
\(\large \quad = (1+P_i^3)\times (1+P_i^1)+P_i^2\)
\(\large \quad = (1+P_i^{\frac{e_i}{2}+1})\times (1+P_i^1+...+P_i^{\frac{e_i}{2}-1})+P_i^{\frac{e_i}{2}}\)
然后我们对第二个单项式递归继续求解即可，
此时我们就能放心大胆地取模哩~
好不容易打了一下午的题解，浅浅要个赞不过分吧qwq
代码部分
.
.
.
.
.
.
.
.
.
自己写awa
特别鸣谢
教练
劳什子
完结撒花✿ヽ(^ ▽^)ノ✿✿
来源：https://www.cnblogs.com/cao2333/p/19888619 |
发表于 2026-4-18 17:23:00