计算指数次方的约数之和模9901

"约数之和的计算方法与C++实现" 给定的题目是一个算法问题，要求计算自然数A的B次方(A^B)的所有约数之和(S)模9901的值。这涉及到数论中的约数求和问题以及快速幂算法的运用。 首先，我们需要理解约数之和的计算方法。对于一个正整数n，其约数之和可以通过分解质因数得到。将n分解为质因数的乘积，例如n=p1^a1 * p2^a2 * ... * pk^ak，其中pi是质数，ai是相应的指数。每个质因子的指数aj对应的约数之和可以用以下公式表示： sum(pj^aj) = (pj^(aj+1) - 1) / (pj - 1) 这个公式适用于任何质因子pj的指数aj。若aj为偶数，可以进一步优化为： sum(pj^aj) = (qmid(pj, aj/2) + 1) * sum(pj, aj/2) 其中，qmid()是快速幂运算，用于高效地计算a^b模m。 在给出的C++代码中，首先定义了两个整数变量A和B来存储输入的值，然后使用一个`unordered_map`来存储质因子及其出现的次数。`divide()`函数用于质因子分解，它通过试除法找到所有能整除n的质因子并更新primes映射。接着，`qmid()`函数实现了快速幂运算，而`sum()`函数用于计算给定质因子次数的约数之和。 在主函数`main()`中，首先读取A和B的值，然后对A进行质因子分解。接着，遍历`primes`映射，对于每个质因子p，其对应的指数k乘以B，这样可以得到A^B的约数中p的指数。利用`sum()`函数计算这些约数之和，并累乘到结果res中。最后，如果A等于0，根据题目要求将结果设为0。输出res即为S mod 9901的值。 这个算法的关键在于质因数分解和快速幂运算，它们大大提高了算法的效率，使其能在给定的数据范围内（0≤A,B≤5×10^7）有效运行。