一个关于能整除个数的数学式子推导,式子已给出,

2个回答

  • 大概给你说说吧,这题看着不那么容易.

    假设一个数n,它的质因子(你题中v[n]所谓的最大因子,应该也是质因子吧)从小到大分别为p1,p2,p3...一直到pn,那么n=(p1^a1)×(p2^a2)×(p3^a3)×...×(pn^an).

    到这里,有一个公式你必须知道,那就是如果n表示为我说的这种形式,那么你题中所谓的f[n]一定满足f[n]=(a1+1)×(a2+1)×(a3+1)×...×(an+1).为什么呢?因为能整除n的数一定是由n的某几个质因子的某次幂乘积而来的(比如1,就是所有质因子的0次幂的乘积),那么,对于一个数x,只要满足x=(p1^x1)×(p2^x2)×(p3^x3)×...×(pn^xn),其中x1是从0到a1的任何一个整数,x2是从0到a2的任何一个整数,x3是从0到a3的任何一个整数...xn是从0到an的任何一个整数,则x一定是n的因子,那么x一共有多少种呢?就是我前面说的f[n]的表达式.

    知道这个下面两个表达式就容易了.

    对于最大因子数大于等于2,也就是我给出的f[n]中an大于等于2呗,v[n]就是我给出的pn呗.

    则有f[n/v[n]]=f[(p1^a1)×(p2^a2)×(p3^a3)×...×(pn^(an-1))]=(a1+1)×(a2+1)×(a3+1)×...×an

    且有f[n/v[n]/v[n]]=f[(p1^a1)×(p2^a2)×(p3^a3)×...×(pn^(an-2))]=(a1+1)×(a2+1)×(a3+1)×...×(an-1)

    那么,f[n]=(a1+1)×(a2+1)×(a3+1)×...×(an+1)=(a1+1)×(a2+1)×(a3+1)×...×an+(an+1)=(a1+1)×(a2+1)×(a3+1)×...×1=f[n/v[n]]+[(a1+1)×(a2+1)×(a3+1)×...×an-(a1+1)×(a2+1)×(a3+1)×...×(an-1)]=f[n/v[n]]+(f[n/v[n]]-f[n/v[n]/v[n]])

    对于最大因子数小于2,小于2那就是1呗,要不然如果是0还谈什么最大因子啊,就是an=1呗.

    那么n=(p1^a1)×(p2^a2)×(p3^a3)×...×pn,f[n]=(a1+1)×(a2+1)×(a3+1)×...×2

    f[n/v[n]]=f[(p1^a1)×(p2^a2)×(p3^a3)×...×(pn^(an-1))],注意an-1=0,所以就不能算进去啦.

    也就是f[n/v[n]]=f[(p1^a1)×(p2^a2)×(p3^a3)×...×p(n-1)^a(n-1)](这里最后的两个(n-1)都是下标)=(a1+1)×(a2+1)×(a3+1)×...×(a(n-1)+1),再乘以2不就是f[n]?

    再好好想想吧.