今天我们来讲一点轻松的事情。事情的经过是这样的，有一天carolz同学在开心地逛微博的时候，看到了一个消息：

【资讯】日本的IT人才求职网站paiza上公布了个免费美少女养成游戏叫《码农把妹（プログラミングで彼女をつくる）》，回答妹子提出的编程问题就能提高好感度，解开发型、服装、台词等道具……

然后她就被岛国人民神(xiu)奇(chi)的创意给折服了。咦，这跟小时候玩的美少女换装游戏有什么不同呢？然后她默默地点开了链接。噢，一看就好想(xiu)玩(chi)哦。于是赶快注册了一个账号玩了起来。

随便截个图给你们感受一下：

paiza

顺便说一下：支持25种语言！25种！总有一款适合你。大约由于是免费体验版，题目难度都不太高，都是些a+b problem难度的题，给你体验一下这个游戏是怎么回事。当然主要的困难之处是在于语言不通（日语无能）。不过看看样例都能猜个大差不差，随便打打也就过去了。不一会儿她就碰到了最终关-水着！也就是泳装啦~【好羞耻。

想看妹子穿泳装，题目的画风都变得不一样了好么！光长度就比前面的problem都长好多了好么。但是大意就是说：

给一个正整数N(1<=N<=1000000)，求N!末尾不为0的9位数（艾玛，中文好简洁）。

这里直接给大家截一下题目中举个栗子：

example

就是给了38的阶乘，然后去掉末尾0，然后删掉前面的保留最后9位，最后去掉前导零输出。

首先，直接求阶乘一定是会爆掉的。毕竟N会有10^6这么大。但是暴力赛高~于是我们决定写一个不那么暴力的暴力。我们设置i从1到N，每次乘以i之后都把结果末尾的0删去，然后对10^9取模。题目中给的样例都过了之后，提交！然后第一组数据就挂掉了（一共5组）。这是为什么捏？为什么捏？后来霞巨巨告诉我说，试试把一开始的模数改到10^10，最后对结果模10^9呢？然后我发现并没有什么卵用，依然没有数据过。但是霞巨巨的提醒是有道理的（道理我们等下再说），于是我决定模个10^11试试看。这么一试就过了。然后思考的时间就到了。是不是模10^11就够了呢？是不是因为数据弱所以过了呢？

让我们先回到为什么要先模一个大一点的数这个问题上。因为在计算的过程中我们可能会突然乘到一个因数含有5的幂的数，记为C*5^a（其中C不能被5整除）。由于在N!中，2的幂一定比5的幂多。因此乘积一定会比乘之前的结果在末尾上多a个0。由于这些0是要被删去的，一旦相乘之后多出来的位数不够补删去的0的个数，结果就会出错。

举个栗子，比如我们算390625!，即(5^8)!，乘到390625的时候，肯定比390624!的结果后面多8个0。若我们对390624!的结果去末尾0后保留后9位，记为S，那么390625*S至少会比S多出5位。因此，390625*S至少有9+5=14位。而这14位中，后8位都是0，是要被删掉的，只剩下14-8=6位数了，于是精度遭受了极大的打击，结果就错掉了。于是我们要在计算中间结果的时候多保留几位以避免这种情况的发生。那么保留多少位合适呢？保留太多了可是要爆精度的。我们可以根据题中N的范围来算一算。易见，末尾0的个数只跟因数中5的次幂有关，所以我们把10^6以内所有5的幂都列出来：

幂 指数(末尾多出的0的个数) 乘以S至少比S多几位 二者差
5 1 0 1
25 2 1 1
125 3 2 1
625 4 2 2
3125 5 3 2
15625 6 4 2
78125 7 4 3
390625 8 5 3

因此我们知道了需要至少为中间结果多保留3位才不会出错。因此中间结果的模数是10^(9+3)=10^12。然后稍微看一下用10^12乘以最大的N，即10^6刚好是10^18不会爆long long。艾玛简直完美。于是问题就解决了。

代码就贴在后面了，泳装的图我就不贴了，想看自己去打题吧~祝大家好运。

++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
long long ans = 1;
long long mod9 = 1000000000; 
long long mod12 = 1000000000000;
int main(){
    int n;
    cin >> n;
    for(long long i = 1; i<=n; i++){
        ans *= i;
        while(ans%10 == 0) ans /= 10;
        ans %= mod12;
    }
    ans %= mod9;
    cout << ans << endl;
    return 0;
}

当然你如果发现窝写的不对，请及时告诉窝！【我才不会说其实数据很弱我已经看到泳装了呢。

谢谢大家~【谢幕