文章poj1845 sumdiv 题解分享给大家，欢迎收藏极客资料网，专注分享技术知识

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 进行 唯一分解

还是拆开好看：

——其中\(P_i\) 表示A的质因子，\(e_i\)表示该质因子的次数。

那\(A^B\)就是给每个\(e_i\)乘上一个B就好了。

应该没人不知道这个吧

很显然地，A的 因子 就是一个x，使得：

其中\(v_i < e_i\).

Emmm...还是不好求嘞...

---

求解

题目要求我们求所有x的和，

每个\(P_i\)会被算:

引入一个另外的一次质因子\(P_j\), 与上面组合，答案就是：

可以发现，\((2)=(1)\times P_j\).

那么多次的\(P_j\)就是：

嘿，您猜怎么着， 咱把这 (1) 一提:

诶呦喂，瞧瞧，我是不是在哪遇见过您？awa

这就是变了个样的 (1) 啊!

噫嘘兮，情乎喜哉！数论之易，易于切水题。

很好，我们只要求每个\(P_i\)所对应的(i),对其求积就可以了。

应该吧QAQ

---

拓展

没想到吧，这篇题解还有拓展awa

上面我们已经求出了这个解释，我还有什么要说的呢?

注意：

\[(I) = 1+P_i^1 + P_i^2 + P_i^3 + ... + P_i^{e_i} \]

有没有发现什么端倪?

oi,这不是个等比数列吗

知道我要说啥了吧awa

(2)-(1),得

那么有

...太丑了吧

虽然丑，但它好求啊，这不比一个一个枚举快多了qwq

其实看有好多大佬还用了 乘法逆元 二次化简，我这个蒟蒻没学过就不在这里做洋相了

好不容易打了一下午的题解，浅浅要个赞不过分吧qwq

代码部分

.

.

.

.

.

.

.

.

.

自己写awa

特别鸣谢

教练

劳什子

完结撒花✿ヽ(^ ▽^)ノ✿✿

文章来源:https://www.cnblogs.com/cao2333/p/19888619
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！