一个关于能整除个数的数学式子推导,式子已给出,f[n] 表示n这个数有多少个数能整除它,比如f[8]=4(1,2,4,8).v[n] 表示n这个数的最大因子,比如f[6]=3;f[n/v[n]]+(f[n/v[n]]-f[n/v[n]/v[n]]); (最大因子次
来源:学生作业帮助网 编辑:六六作业网 时间:2024/09/07 19:29:55
一个关于能整除个数的数学式子推导,式子已给出,f[n] 表示n这个数有多少个数能整除它,比如f[8]=4(1,2,4,8).v[n] 表示n这个数的最大因子,比如f[6]=3;f[n/v[n]]+(f[n/v[n]]-f[n/v[n]/v[n]]); (最大因子次
一个关于能整除个数的数学式子推导,式子已给出,
f[n] 表示n这个数有多少个数能整除它,比如f[8]=4(1,2,4,8).
v[n] 表示n这个数的最大因子,比如f[6]=3;
f[n/v[n]]+(f[n/v[n]]-f[n/v[n]/v[n]]); (最大因子次数大于等于2)
f[n]=
f[n/v[n]]*2; (最大因子次数小于2)
一个关于能整除个数的数学式子推导,式子已给出,f[n] 表示n这个数有多少个数能整除它,比如f[8]=4(1,2,4,8).v[n] 表示n这个数的最大因子,比如f[6]=3;f[n/v[n]]+(f[n/v[n]]-f[n/v[n]/v[n]]); (最大因子次
大概给你说说吧,这题看着不那么容易.
假设一个数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]?
再好好想想吧.
好难啊,明天问老师吧!