Sumdiv（经典数学问题，快速幂，唯一分解定理，约数和定理，递归求等比，同余模公式）

Sumdiv（经典数学问题，快速幂，唯一分解定理，约数和定理，递归求等比，同余模公式）

题目描述 有两个自然数a和b(a,b≤50000000)求a的b次方的所有约数之和模9901输入格式 一行，包含由空格分隔的两个自然数a和b输出格式 一行，a的b次方的约数和模9901样例输入 2 3样例输出 15样例解释 8的约数是1,2,4,8， 它们的总和是1515模9901是15

题意：求A^B的所有约数之和。 用到的知识: 1，唯一分解定理: A=(p1n1p2n2p3n3…pknk); 把底数A分解 其中pi为素数 2，约数和定理：就是把A所有的约数 由上面我们，我们可以得出A=(p1n1p2n2p3n3…pknk)； sum=(1+p11+p12+……p1n1) * (1+p21+p22+……p2n2) * ……(1+pk1+pk2……+pknk); 3,同余模公式: (a+b)%m=(a%m+b%m); (ab)%m=(a%mb%m);

解法：

1.素因子分解

A首先对第一个素数2不断取模，A%2==0时 ，记录2出现的次数+1，A/=2；（这样会节省一部分时间） 当A%2!=0时，则A对下一个连续素数3不断取模…

以此类推，直到A==1为止。

注意特殊判定，当A本身就是素数时，无法分解，它自己就是其本身的素数分解式。

2.求a^b的所有约数之和

用递归二分求等比数列1+pi+pi^2+pi^3+...+pi^n：

（1）若n为奇数,一共有偶数项，则： 1 + p + p^2 + p^3 +…+ p^n = (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +…+ p^(n/2) * (1+p^(n/2+1)) = (1 + p + p^2 +…+ p^(n/2)) * (1 + p^(n/2+1))

上式红色加粗的前半部分恰好就是原式的一半，那么只需要不断递归二分求和就可以了，后半部分为幂次式，将在下面第4点讲述计算方法。 （2）若n为偶数,一共有奇数项,则: 1 + p + p^2 + p^3 +…+ p^n = (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +…+ p^(n/2-1) * (1+p^(n/2+1)) + p^(n/2) = (1 + p + p^2 +…+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2); 上式红色加粗的前半部分恰好就是原式的一半，依然递归求解

#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。