根据d(n)和σ(n)能否给出因数分解式

manthanein

给定正整数n和d(n)、σ(n)的值，问能否得出n的因数分解式？

.·.·.

能说一下d(n)、σ(n)的定义吗？
高中时候可能还熟
现在已经忘光了

manthanein

.·.·. 发表于 2018-12-9 13:41
能说一下d(n)、σ(n)的定义吗？
高中时候可能还熟
现在已经忘光了

d(n)是所有约数的数量，σ(n)是它们的和
比如d（6）=4
σ(6)=1+2+3+6=12

.·.·.

暂时只会d=1（1），2（素数），3（对n开根号），4（如果不能开立方根，设p+q=σ(n)-n-1,p*q=n，解方程）5（开四次方根）
6（尝试开五次方根，若不行，则d(n)=(1+p)(1+q+q^2)=(1+n/q)(1+q+q^2)，如果允许解一个三次方程，这个题还有救）
7，开六次方根
8……
七次方根
若不行，尝试d(n)=(1+p)(1+q+q^2+q^3)解四次方程
还不行，尝试d(n)=(1+p)(1+q)(1+r),n=pqr，这时候分解起来就比较吃力了，因为没有方程可以解了
这时候或许可以尝试找到d(n)的一个比较大的因子（比如用ECM算法），之后从这个因子出发暴力搜索n能否整除（这个因子的某个倍数减1）
……
或许这时候直接上MSIEVE.EXE会快一点