阶乘的最右一位非零数字求和

yuxh

Problem
对于小于25000的自然数n,求阶乘n!,(n-1)!,(n-2)!...3!,2!,1!最右边的非零数之和。

例如：

当n=5时，
5!=120,右边非零数为2;
4!=24,右边非零数为4;
3!=6,右边非零数为6;
2!=2,右边非零数为2;
1!=1,右边非零数为1。
其右边的非零数之和为15。

Input
本题有多组数据，每组数据包含一个正整数N(N不大于25000)占一行。

Output
对给定的每组输入数据，输出一个整数。每个结果占一行。不要输出额外的空行。

Sample Input
5
10
1

Sample Output
15
39
1

部份结果如下:
11
47

111
543

1111
5547

11111
55567

111111
555455

1111111
5555481

11111111
55555817

111111111
555555081

1111111111
5555555731

11111111111
55555555603

111111111111
555555554817

1111111111111
5555555553031

11111111111111
55555555553495

yuxh

容易得到O(nlog(n))的算法:

1. int fac2[] = {6,2,4,8};
   
2. int fac[] = {1,1,2,6,4};
   
3. 
   
4. long long calc(long long n)
   
5. {
   
6.     long long s = 1, i, t;
   
7.     int v=1, k=0, l=0;
   
8.     for(i=2; i<=n; i++) {
   
9.         for(t=i; t%2==0; t/=2) k++;
   
10.         for(;t%5==0; t/=5) l++;
    
11.         v = ((t%10) * v) % 10;
    
12.         s += (v * fac2[(k-l)%4]) % 10;
    
13.     }
    
14.     return s;
    
15. }
    
16. 
    
17. int main()
    
18. {
    
19.     long long n;
    
20.     printf("input n:");
    
21.     scanf("%lld", &n);
    
22.     printf("result:%lld\n", calc(n));
    
23. }

复制代码

但问题是如何得到O(log(n))的算法
很有趣的题目,花了我整整两天~~~

yuxh

O(log(n))的算法过会儿再给出
容我卖个关子啊~

win_hate

x=2^l 5^n *y

(l, n, y mod 10)
2^l mod 10: 1->2, 2->4, 3->8, 4->6

1: (0, 0, 1) -> 1
2: (1, 0, 1) -> 2
3: (1, 0, 3) -> 6
4: (3, 0, 3) -> 4
5: (3, 1, 3) -> (2, 0, 3) -> 2
6: (4, 1, 9) -> (3, 0, 9) -> 2
7: (3, 0, 3) -> 4
8: (6, 0, 3) -> 2
9: (6, 0, 7) -> 8
10: (6, 0, 7)-> 8
11: (6, 0, 7) -> 8

win_hate

这个估计跟 yuxh 给出的代码背后的想法是一致的。

我就等着看 O(log N) 了,

jkit

解法一：
第一步，对于所有的数（根据题意<25000）先用O(nlog(n))的算法算出来将结果保存到文件里面去。
第二步，以后每次需要的时候，直接从结果文件里面检索。

解法二：

申明数组用于保存每个数对应的结果
读取一个数，
如果这个数小于当前已经算过的数，那么直接返回数组里面对应的结果
如果大于当前已经算过的数，那么从当前已经算过的数一直算到这个数，并且把每个数的结果保存到数组里面去。

[ 本帖最后由 jkit 于 2006-5-16 09:22 编辑 ]

yuxh

我得到的O(log(n))的程序:

1. int fac2[] = {6,2,4,8};
   
2. int facn[] = {6,6,2,6,4};
   
3. long long cnt[30][4]={{1,1,3,0}}, cnt_len = 1;
   
4. int co_list[30], list_len=0;
   
5. 
   
6. int get_val(int v, int b, int k)
   
7. {
   
8.     v = v * facn[b] * fac2[(k*b)%4] % 10;
   
9.     return v;
   
10. }
    
11. 
    
12. void preproc(long long n)
    
13. {
    
14.     int k, i, j, mul;
    
15.     for(k=0; n>0; n/=5, k++) {
    
16.         co_list[k] = n%5;
    
17.         if(k >= cnt_len) {
    
18.             memset(cnt[k], 0, sizeof(long long)*4);
    
19.             for(j=0; j<5; j++) {
    
20.                 mul = get_val(1, j, k);
    
21.                 for(i=0; i<4; i++)
    
22.                     cnt[k][((mul*2*(i+1))%10)/2-1] += cnt[k-1][i];
    
23.             }
    
24.             cnt_len++;
    
25.         }
    
26.     }
    
27.     list_len = k-1;
    
28. }
    
29. 
    
30. long long calc(long long n)
    
31. {
    
32.     int i, j, k, mul = 1, v=1;
    
33.     long long val = 0, part[4];
    
34.     preproc(n);
    
35.     memset(part,0,sizeof(part));
    
36.     for(i=list_len; i>0; i--) {
    
37.         for(j=1; j<=co_list[i]; j++) {
    
38.             mul = get_val(v, j-1, i);
    
39.             for(k=0; k<4; k++) {
    
40.                 part[((mul*2*(k+1))%10)/2-1] += cnt[i-1][k];
    
41.             }
    
42.         }
    
43.         v = get_val(v, j-1, i);
    
44.     }
    
45.     for(j=0; j<=co_list[0]; j++) {
    
46.         mul = get_val(v, j, 0);
    
47.         part[mul/2-1]++;
    
48.     }
    
49.     val += 2*part[0] + 4*part[1] + 6*part[2] + 8*part[3] - 11;
    
50.     return val;
    
51. }
    
52. 
    
53. int main()
    
54. {
    
55.     long long n;
    
56.     while(1){
    
57.         printf("input n:");
    
58.         scanf("%lld", &n);
    
59.         if(n == 0) break;
    
60.         printf("result:%lld\n", calc(n));
    
61.     }
    
62. }
    

复制代码

提示:
用f(n)表示n!的最右不为0的数字,则可以得到下面的公式:

设n=Ak*5^k+...+A1*5+A0(0<=Ai<=4)为其5进制展开
则f(n)=f(A0)f(A1)...f(Ak)*2^(A1+2A2+...+kAk)%10

win_hate

to yuxh:

设 n = 5*q + r， 则

f(n) = r!*f(q) 2^q    mod 10

q = (A_K...A_1)，注意到 2^5 = 2 mod 10，所以上式子也可以写为(r=A_0)：

f(n) = (A_0!) * f(q) 2^{A_1+...+ A_k}   mod 10                (R)

而在这个的基础上迭代就可以得到你给出的公式。

直接用公式 R 计算 f(n) 很快，但求 sum  的时候就慢了，因为要不断除5。在一开始就使用 5 进制，可以避免对每个 n 进行拆分。从 n 过渡到 n-1，只需要把 A_0 减去 1 并做进位处理。效率上的改善主要体现在这里，对吗？


我没看懂你的代码，只是从你给出的公式进行分析的，你看看我的理解是否与你的一致？能不能说一下你的代码？你是把每一个 f(n) 都求出来了还是怎么的？

单纯求 f(n) 我有一个类似的公式，但用来求和也比较慢。

yuxh

气死我了
打了半天的字，一发送，报告来路不正。。。

win_hate

呵呵，先保存一下嘛。

看看这个：

g(n) 表示 n! 分解中不含因子 5 的部分，若 n =(A_k....A_0)_5 则

g(n) = A_0! * g (A_k ... A_1)_5

这样就可以用动态规划把 g(n) 求出来。 _5 表示 5 进制