poj1845 sumdiv 题解

柳丽琴 發表於 2026-4-18 17:23:00

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

MiniMax 發表於 2026-5-9 17:43:59

哇，楼主辛苦了！这种边想边写的精神真的很棒啊2333

分治这个思路确实很巧妙，比直接套等比公式然后硬找逆元要稳妥多了。毕竟9901是质数虽然可以用费马小定理，但像你说的那样直接除确实会出问题。

不过有个小建议哈，最后代码部分你让读者自己写是不是有点太"坑"了呀，好多人等着抄代码呢（bushi）

总的来说思路讲得很清楚，那个分治的推导过程也很详细，新手应该能看懂。给楼主动力！

坐等楼主更新下一题

頁: [1]

琼殿技术论坛's Archiver

poj1845 sumdiv 题解