USACO Section 3.2 Factorials

Factorials

The factorial of an integer N, written N!, is the product of all the integers from 1 through N inclusive. The factorial quickly becomes very large: 13! is too large to store in a 32-bit integer on most computers, and 70! is too large for most floating-point variables. Your task is to find the rightmost non-zero digit of n!. For example, 5! = 1 * 2 * 3 * 4 * 5 = 120, so the rightmost non-zero digit of 5! is 2. Likewise, 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040, so the rightmost non-zero digit of 7! is 4.

PROGRAM NAME: fact4

INPUT FORMAT

A single positive integer N no larger than 4,220.

SAMPLE INPUT (file fact4.in)

7

OUTPUT FORMAT

A single line containing but a single digit: the right most non-zero digit of N! .

SAMPLE OUTPUT (file fact4.out)

4
Analysis

Considering the small amount of 4,220, we can find that the highest number of zeros is 5 since 5^5<4,220<5^6. What we are interested in is the last 6 numbers after each step of factorial. At last, we may output the last non-zero digit.

Code
/*
ID:braytay1
PROG:fact4
LANG:C++
*/

#include 
<iostream>
#include 
<fstream>
using namespace std;

int main(){
    ifstream fin(
"fact4.in");
    ofstream fout(
"fact4.out");
    
int n;
    
int s;
    fin
>>n;
    s
=1;
    
for (int i=1;i<=n;i++){
        s
*=i;
        
if (s>=100000&&s%10==0{
            
while (s%10==0)    
                s
/=10;
            s
%=100000;
        }

        
else s%=100000;
    }

    
while (s%10==0)    
        s
/=10;
    fout
<<s%10<<endl;
    
return 0;
}


posted on 2008-08-22 20:36 幻浪天空领主 阅读(207) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿(1)

随笔档案(2)

文章分类(23)

文章档案(22)

搜索

最新评论

阅读排行榜

评论排行榜