2018年第九届蓝桥杯省赛B组真题 C题：乘积尾零
乘积尾零
题意：
如下的10行数据，每行有10个整数，请你求出它们的乘积的末尾有多少个零？
5650 4542 3554 473 946 4114 3871 9073 90 4329
2758 7949 6113 5659 5245 7432 3051 4434 6704 3594
9937 1173 6866 3397 4759 7557 3070 2287 1453 9899
1486 5722 3135 1170 4014 5510 5120 729 2880 9019
2049 698 4582 4346 4427 646 9742 7340 1230 7683
5693 7015 6887 7381 4172 4341 2909 2027 7355 5649
6701 6645 1671 5978 2704 9926 295 3125 3878 6785
2066 4247 4800 1578 6652 4616 1113 6205 3264 2915
3966 5291 2904 1285 2193 1428 2265 8730 9436 7074
689 5510 8243 6114 337 4096 8199 7313 3685 211
注意：需要提交的是一个整数，表示末尾零的个数。不要填写任何多余内容。
答案：31 。
方法一：舍弃高位数法。
将100个数字相乘的结果会非常庞大，在计算机中即使使用长整型（long long）也无法存储下这个数值。事实上，在计算过程中产生的大量零都是由于低位数字相乘所致。因此，在每次乘法运算后我们统计并记录产生的零的数量和位置。为了便于后续处理和避免重复记录这些零的位置信息，我们将这些零予以舍弃，并将剩余部分进行处理。为了避免重复记录这些零的位置信息，请在每一步运算结束后只保留高位部分（即计算结果对一百万取模），这样不仅能够有效减少数据量的同时也能保证必要的精度要求。最后一步操作的具体实现可以通过以下步骤来完成：首先将所有中间结果依次累加，并在每一步运算结束后只保留高位部分（即计算结果对一百万取模）。这一步骤可以帮助我们有效地提取所需的部分而不影响最终的结果准确性。
//乘积尾零方法一：
#include<stdio.h>
typedef long long ll;
int main()
{
ll n,s=1;
int L=0;
for(int i=1; i<=100; i++)
{
scanf("%lld",&n);
s=s*n;
while((s%10)==0)
{
s=s/10;
L++;
}
s=s%100000000;//s数太大了，我们只取后面的一些数，前面的忽略不计
}//至于为什么是 100000000
//其实可以自己尝试着开，看看每一次改变这个数（100000000）（加个0，减个0）
//看看L的值会不会改变
printf("%lld\n",L);
return 0;
}
代码解读方法二：分解质因数法。
所有数相乘可以转换成它们各自的因数相乘。
我们观察到产生零的情况源于数字中的2与5相乘。
因此我们需要统计每个数字中包含多少对因数2和因数5。
接着我们找出这些因素中的最小数量即可确定结果中的零的数量。
//分解质因数法
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{
int i,d;
int s5=0,s2=0;
for(i=1; i<100; i++)
{
scanf("%d",&d);
while(d%5==0)
{
s5++;//因数为5的个数
d=d/5;
}
while(d%2==0)
{
y2++;//因数为2的个数
d=d/2;
}
}
int k=min(s5,s2);
printf("%d\n",k);
}
代码解读