阶乘问题[计算1-1000000]

阶乘问题(fact)

时间限制: 1 Sec  内存限制: 64 MB
提交: 66  解决: 16

题目描述

阶乘的定义如下：N!=l×2×3×…×N-1×N
例如，12!=1×2×3×4×5×6×7×8×9×10×11×12=479001600
最右的非0位是6，后面有2个0。
写一个程序计算N!最右非0位和末尾的0的个数。

输入

一个整数N，1≤N≤1000000。

输出

1行，输出2个整数：最右非O位，末尾0的个数。

样例输入

12

样例输出

6 2
----------
如何获得末尾0的个数？
jio个例子:
1！----》1
2！----》2
3！----》6
4！----》24
5！----》120
观察一下不难发现

1！----》1
2！----》2　　的因子为2，末尾没有0
3！----》6　　的因子也有2，末尾没有0
4！----》24　　的因子也有2，末尾还是没有0
5！----》120　　的因子有2，有5，末尾有一个0
7!……
8!……
【都没有再出现因子5】
所以末尾都还是只有1个0
9!……
当10!时,10!=9!*10=9!*（2*5）【这里出现了5,加上之前有出现2,所以现在开始末尾有2个0了】
以此类推,所以0的个数取决于5的因子出现的次数.
准确的说那0的个数其实就是来自：（2*5）=10进的位数.

那么，我们不可能发现了这种规律还是用一个数一个数乘把，我们只需要计算阶乘时候的那些数的因子2和因子5就可以了；
所以

public static int zeroft(int n,int y) {//y为计算因子(2 or 5);
        int i,t,c = 0;
        for(i=1;i<=n;i++) {
            t=i;
            while(t%y==0) {
                c++;
                t/=y;
            }
        }
        return c;//返回因子y的个数；
    }

下面是计算末尾的非0；

public static long nozero(int n) {
        long i,t=1;
        for(i=1;i<=n;i++) {
            t*=i;
            while(t%10==0) {
                t/=10;
            }
            t%=1000000;//这里主要就是当这个数特别大，甚至大到可能超过long的情况下事先对其约束位数，通俗的将就是将大于7位的数的前面那段数给去掉；进过验证发现，处理后的数的末尾
的非0数与未处理的数的末尾的非0位一样；
        }
        return t%=10;//对最后结果取末尾数;
}

完整代码:

import java.util.Scanner;

public class Sd {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt(),a=zeroft(n,2),b=zeroft(n,5);
        int c=a>b?b:a;
        System.out.println(nozero(n)+" "+c);
    }
    public static int zeroft(int n,int y) {
        int i,t,c = 0;
        for(i=1;i<=n;i++) {
            t=i;
            while(t%y==0) {
                c++;
                t/=y;
            }
        }
        return c;
    }
    public static long nozero(int n) {
        long i,t=1;
        for(i=1;i<=n;i++) {
            t*=i;
            while(t%10==0) {
                t/=10;
            }
            t%=1000000;
        }
        return t%=10;
    }
}