POJ 1845 – Sumdiv

题目链接:POJ 1845

题意是给出$a$和$b$,求$a^b$的所有因子的和,输出这个和对9901取模的结果。

根据质数唯一分解定理,$a$一定可以写成这样的形式:

$$ a = p_{1}^{k_1} p_{2}^{k_2} \cdots p_{n}^{k_n} $$

其中$p_i$为素数。那么

$$a^b=(p_{1}^{k_1} p_{2}^{k_2} \cdots p_{n}^{k_n})^b =p_{1}^{bk_1} p_{2}^{bk_2} \cdots p_{n}^{bk_n}$$

则$a^b$所有因子的和为

$$S = \prod_{i = 1}^{n} \left( \sum_{j = 0}^{bk_i} p_{i}^{j}  \right)  =\prod_{i = 1}^{n} \frac{p_{i}^{bk_i + 1} – 1}{p_i – 1}$$

$$\Rightarrow S \mod P = \left( \prod_{i = 1}^{n} \frac{p_{i}^{bk_i + 1} – 1}{p_i – 1} \right) \mod P = \left[ \prod_{i = 1}^{n} \left( \frac{p_{i}^{bk_i + 1} – 1}{p_i – 1} \mod P \right) \right] \mod P $$

所以,关键在于求解$\frac{p_{i}^{bk_i + 1} – 1}{p_i – 1} \mod P$。不难发现这里$P=9901$是一个素数,所以根据费马小定理

$$b^P b^{-1} \mod P = 1$$

那么

$$a b^{-1} \mod P = a b^{-1} b^{P} b^{-1} \mod P = a  b^{P-2} \mod P \tag{1}$$

考虑到 $b$ 是 $p$ 的倍数时,$b$在模$P$意义下的逆元不存在,需要使用

$$a b^{-1} \mod P = \frac{a \mod (P \cdot b)}{b} \tag{2}$$

特别注意,逆元存在时候用公式$(1)$,不存在的时候用公式$(2)$。

 

说点什么

avatar
50
  Subscribe  
提醒