已知条件:n=p1^a1xp2^a2xp3^a3........xpk^ak; 求解 n 的因数的个数;
求解的主要思想:递归
设所有的因数的个数为 U1;
则 U1 会等于什么呢?
不妨设求得 p2^a2xp3^a3.......xpk^ak=U2;
则我们可以这样考虑:
U1 包含 3 部分:1. 只有 p1 的因素:共有 a1 种(无非是 p1,p1*p1,...)
2. 不包含 p1: 共有 U2 种
3. 包含 p1, 但不只是 p1: 共有 a1xU2 种(对于 U2 中的每一种情况加乘有 p1 的项,就会构成新的一个因数)
也许你会有疑问,假如有重复怎么办?答案是不可能的,因为如果重复的那个数是 m,则 m 存在多种素因数分解式,显然矛盾.
因此,我们可以得到一个递推式:U1=a1+U2+a1xU2=a1+(a1+1)U2; 但是,有没有注意到,所有的因数都没有包含 1,显然我们上面所包含的因素都大于 1;
所以设 n 的所有素因数的个数为 C 则 C=U1+1;
又递推可知:U2=a2+(a2+1)U3
...............................................
以上递推式可解得:U1=a1+a2x(a1+1)+a3x(a2+1)x(a1+1)+.......+akx(a[k-1]+1)x(a[k-2]+1)x....(a1+1)
C=U1+1=a1+1+a2x(a1+1)+.....=(a1+1)x(a2+1)+........
发现了吧: 最后 C=(a1+1)x(a2+1)x(a3+1).........x(ak+1)
以上就是借助递归思想进行求解的过程,可见递归还是很强大的.
来源: https://www.cnblogs.com/cittysteven/p/8278114.html