[POJ1845]Sumdiv[约数,逆元]

题面

算数基本定理的推论: 正整数N被唯一分解为$latex p_1^{c_1}*p_2^{c_2}*…*p_m^{c_m}$的所有约数的和为$latex \prod_{i=1}^{m}(\sum_{j=0}^{c_i}p_i^j)$

(可由N的正约数集合元素之和因式分解得到)

本题求$latex A^B$约数和只要把指数乘个B,再用等比数列求和公式. 本题模数为质数, 求逆元时可以直接用费马小定理.

几个要注意的细节见代码注释.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址