- 论坛徽章:
- 1
|
公式的推导基本是正确的，下面看怎么用这个公式
为方便起见，下面的函数之间的*乘法是指模10的运算，即m*n=(m%10) * (n%10) % 10
可以看到，f(n)有下面的属性：若在m和n的5进制展开Ak, Bk中没有相同的阶，即不存在i， 使Ai>0, Bi>0同
时成立，则f(m+n)=f(m) * f(n)，特殊情况下，f(Ak*5^k+...+Ai*5^i +...+A0)=f(Ak*5^k + ... + A_(i+1)*5^(i+1)) * f(Ai*5^i + .. + A0) （F）
另外，由于在n!的因子中，2的个数一定比5的个数多，所以，若n>1，则f(n)的值只能是2、4、6、8，又6*n=n (n=2,4,6, ，所以6具有1的性质，为了统一起见，我们定义f(0) = f(1) = 6，而不是1，这样最终的结果会多出6*2-1=11
设s(m,n)=f(m) + f(m+1) + ... + f(m+n-1)，若m的5进制展开中最低阶比n的最高阶要大，则由（F），得到
s(m,n) = f(m)*f(0) + f(m)*f(1) + ... + f(m)*f(n-1)，可以看到每个因子都差了一个常数f(m)
如果我们知道f(0), ... f(n-1)中2、4、6、8的个数，则计算f(m)后，可以得到s(m,n)的2、4、6、8的个数
如：s(0,5)=6+6+2+6+4，其中2有1个，4有1个，6有3个，8有0个，记录到数组cnt中，初始值为cnt[0]={1,1,3,0}，如果要求s(5^2)，则
s(5^2) 分成0-4, 5-9, 10-14, 15-19, 20-24 五个部份
由第一部份，得到1 1 3 0
由第二部份，f[5]=2，2分别与2、4、6、8相乘，得到4 8 2 6， 于是得到4有1个，8有个1，2有3个，6有0个，即3 1 0 1
同样，由第三部份，得到1 0 1 3
第四部分，得到1 0 1 3
第五部份，得到0 3 1 1
相加的和，得到6 5 6 8
用这个方法可以得到s(0,5^k)的结果，记入到数据cnt中
于是：
设n的5进制展开式为Ak*5^k + ... + A1 * 5 + A0，则
s(0,n)=s(0,Ak*5^k) + s(Ak*5^k, A_(k-1) * 5^(k-1)) + ... +s(Ak*5^k+...+A1*5, A0)
用相同的方法可以得到2、4、6、8的个数，记入数组part
于是sum(n)=2*part[0] + 4*part[1] + 6*part[2] + 8*part[3] - 11 |
|
免费注册
发表于 2006-05-15 19:57
