一个关于能整除个数的数学式子推导,式子已给出,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/06/30 10:08:44
![一个关于能整除个数的数学式子推导,式子已给出,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]]); (最大因子次](/uploads/image/z/215664-24-4.jpg?t=%E4%B8%80%E4%B8%AA%E5%85%B3%E4%BA%8E%E8%83%BD%E6%95%B4%E9%99%A4%E4%B8%AA%E6%95%B0%E7%9A%84%E6%95%B0%E5%AD%A6%E5%BC%8F%E5%AD%90%E6%8E%A8%E5%AF%BC%2C%E5%BC%8F%E5%AD%90%E5%B7%B2%E7%BB%99%E5%87%BA%2Cf%5Bn%5D+%E8%A1%A8%E7%A4%BAn%E8%BF%99%E4%B8%AA%E6%95%B0%E6%9C%89%E5%A4%9A%E5%B0%91%E4%B8%AA%E6%95%B0%E8%83%BD%E6%95%B4%E9%99%A4%E5%AE%83%2C%E6%AF%94%E5%A6%82f%5B8%5D%3D4%EF%BC%881%2C2%2C4%2C8%EF%BC%89.v%5Bn%5D+%E8%A1%A8%E7%A4%BAn%E8%BF%99%E4%B8%AA%E6%95%B0%E7%9A%84%E6%9C%80%E5%A4%A7%E5%9B%A0%E5%AD%90%2C%E6%AF%94%E5%A6%82f%5B6%5D%3D3%EF%BC%9Bf%5Bn%2Fv%5Bn%5D%5D%2B%28f%5Bn%2Fv%5Bn%5D%5D-f%5Bn%2Fv%5Bn%5D%2Fv%5Bn%5D%5D%29%3B+%EF%BC%88%E6%9C%80%E5%A4%A7%E5%9B%A0%E5%AD%90%E6%AC%A1)
一个关于能整除个数的数学式子推导,式子已给出,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]?
再好好想想吧.
好难啊,明天问老师吧!