时间戳

首页 > 技术文章 > 阶乘问题

阶乘问题

TWS-YIFEI 2016-08-09 10:45 原文

问题 F: 

时间限制: 1 Sec  内存限制: 128 MB
提交: 44  解决: 38
[提交][状态][讨论版]

题目描述

也许你早就知道阶乘的含义，N阶乘是由1到N相乘而产生，如：
    12! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 = 479,001,600
12的阶乘最右边的非零位为6。
    写一个程序，计算N(1<=N<=50,000,000)阶乘的最右边的非零位的值。
注意:10,000,000！有2499999个零。

输入

仅一行包含一个正整数N。

输出

单独一行包含一个整数表示最右边的非零位的值。

样例输入

12

样例输出

6


解题思路：额，写的代码有点长，但思路很好理解。
　　题目要求最多计算到50,000,000的阶乘，最后得到的结果肯定大的不行了。
　　但求的是结果最右边的非零值，那么每次相乘的时候只有最后一位对结果有影响，高位不会影响低位的。
　　所以每次取数的最后一位，按说计算50,000,000次是有点慢的，应该会超时，但我提交竟然AC了。
代码：
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int main()
{
    int n;
    int f=1;
    int b;
    int a1=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        b=i;
        a1=0;
        while(a1==0){
            if(b==10){
                a1=1;
                break;
            }
            if(b==20){
                a1=2;
                break;
            }
            if(b==30){
                a1=3;
                break;
            }
            if(b==40){
                a1=4;
                break;
            }
            if(b==50){
                a1=5;
                break;
            }
            if(b==60){
                a1=6;
                break;
            }
            if(b==70){
                a1=7;
                break;
            }
            if(b==80){
                a1=8;
                break;
            }
            if(b==90){
                a1=9;
                break;
            }
            a1=b%10;
            b/=10;
        }
        f=f*a1;
        b=f;
        a1=0;
        while(a1==0){
            if(b==10){
                a1=1;
                break;
            }
            if(b==20){
                a1=2;
                break;
            }
            if(b==30){
                a1=3;
                break;
            }
            if(b==40){
                a1=4;
                break;
            }
            if(b==50){
                a1=5;
                break;
            }
            if(b==60){
                a1=6;
                break;
            }
            if(b==70){
                a1=7;
                break;
            }
            if(b==80){
                a1=8;
                break;
            }
            if(b==90){
                a1=9;
                break;
            }
            a1=b%10;
            b/=10;
        }
        f=a1;
    }
 
    printf("%d",f);
    return 0;
}
 
/**************************************************************
    Problem: 1821
    User: zz13
    Language: C++
    Result: 正确
    Time:0 ms
    Memory:1696 kb
****************************************************************/

 

 

推荐阅读