AcWing - 97 - 约数之和(分治、因数和)

标签：return   air   algorithm   algo   names   print   clu   sync   memset   

题目链接
??我们首先要知道怎么来求A的约数之和。首先，把A分解质因数，可得：\(A = q1^{k1}\times q2^{k2} ... \times \ qn^{kn}\)
然后我们用乘法的分配律可得A的因数之和为\(F(A) = (q1^0 + q1^1 + ... + q1^{k1}) \times (q2^0 + q2^1 + ... + q2^{k2})\ ... \times \ (qn^0 + qn^1 + ... + qn^{kn})\)
??那么对于\(A^B\)来说，\(A^B = q1^{k1\times B}\times q2^{k2\times B} ... \times \ qn^{kn\times B}\)，\(F(A^B) = (q1^0 + q1^B + ... + q1^{k1\times B}) \times (q2^0 + q2^B + ... + q2^{k2\times B})\ ... \times \ (qn^0 + qn^B + ... + qn^{kn\times B})\)
所以说，我们只要求出来所有因数的所有幂次之和这道题就能很容易的求出来了\(q^0 + q^B + ... + q^{k\times B}\)，但是我们发现\(k\times B\)看起来并不好求，用暴力的方法显然会超时，关于这个式子的求法可以看这里

//https://www.cnblogs.com/shuitiangong/
#include
#include

AcWing - 97 - 约数之和(分治、因数和)

标签：return   air   algorithm   algo   names   print   clu   sync   memset   

原文地址：https://www.cnblogs.com/shuitiangong/p/12538482.html