蓝桥杯2018初赛 乘积尾零

url: http://oj.ecustacm.cn/problem.php?id=1361

tag:
数学

思路：
计算末尾零可以求每个因子中有多少对因子5和因子2，因为2 * 5 = 10，又因为2出现的次数会比5多，因为只要是偶数的情况就会出现因子2.所以只要计算这100个数中，每个数中因子5的个数，然后累加最后输出即可。

对于求阶乘来说，如果是某个数的阶乘，求这个数除以5，25，125……5^k之后累加。例如100除以5之后等于20，那么对于1到20来说每个数乘以5后都会变成一个贡献5因子的数，除以25之后等于4说明1到4中每个数乘25都可以变成一个贡献25因子的数，而25 = 5 5，则是在原来贡献了5因子基础上多贡献一个5，为了避免重复，以及避免漏算，只需要将4 加上 20，即为答案。说明对于100！（1 2 3 …… * 100）来说，一共可以贡献出24个因子5，就是有24个末尾0.这种求阶乘末尾0的方式实际上和本题有出路。

代码：

// 乘积尾零
#include <iostream>
using namespace std;
int main()
{
    int n = 10;
    int cnt = 0;
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < n; j ++)
        {
            int a;
            cin >> a;
            while (a && a % 5 == 0)
            {
                if (a % 5 == 0)
                {
                    a /= 5;
                    cnt ++;
                }
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

答案：

#include <iostream>
using namespace std;
int main()
{
    cout << 31 << endl;
    return 0;
}