乘积尾零（Java详解）

目录

一、题目描述

二、题解

方法一

方法二

---

一、题目描述

如下的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

二、题解

思路分析：

题目要求我们求出这100个数相乘的结果末尾有多少个零，因此我们只需关注末尾的零。若直接相乘最后求乘积的末尾有多少个零，由于相乘所得数据太大，会导致溢出，因此不能通过直接求所有数乘积的方法来求得尾零个数，那该如何求出尾零的个数呢？

方法一

由于直接相乘所得的数据太大，因此我们可以每乘上一个数，就计算乘积的结果末尾有多少个零，由于结果末尾的零不影响前面数字的运算，我们使用计数器count加上结果末尾的零后，就可将尾部的零去除，用去除末尾零后的结果继续计算

但即使如此，因为相乘的100个数较大，每次去除零后再相乘，结果也很大，也可能会溢出，由于结果最前面的位数也不会影响结果末尾0的个数，因此我们可以将结果 %10000 ，去除结果前面的位数，防止结果溢出

具体实现：

使用计数器count统计尾零的个数，遍历这100个数，每乘上一个数就统计其尾零的个数，计数器相加，并去除尾零，再将结果%10000，去除前面的位数

代码实现：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
       int count = 0;//统计尾零的个数
       int m = 1;//乘积
       for(int i = 0; i < 100; i++){
           int n = scan.nextInt();
           m *= n;
           //统计零的个数，并去除m的尾零
           while(m > 0){
               if(m % 10 == 0){
                   count++;
               }else{
                   break;
               }
               m /= 10;
           }
           //去除m前面的位数，防止溢出
           m %= 10000;
       }
       System.out.println(count);
       scan.close();
   }
}

方法二

为什么两个数相乘的结果末尾会有0？

因为这两个数字的约数里有2和5，10 = 2*5，一个2和一个5相乘产生一个末尾0，有多少对2和5，结果的末尾就会有多少个0。

例如：

40 = 2*2* 2*5（一对2和5）

30 = 3 * 2*5 （一对2和5）

100 = 2*5 * 2*5；（两对2和5）

因此，我们只需要计算这100个数中有多少个2和多少个5，再取其最小值，得到一共有多少对2和5，就可得出乘积的尾零个数

具体实现：

（1）遍历这100个数，分别求出2和5的个数

（2）求出2和5个数中的最小值，就可得出乘积的尾零个数

代码实现：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
       //分别统计2和5的个数
       int twoCount = 0;
       int fiveCount = 0;
       for(int i = 0; i < 100; i++){
         int n = scan.nextInt();
         int m = n;
         while(n % 2 == 0){
           twoCount++;
           n /= 2;
         }
         while(m % 5 == 0){
           fiveCount++;
           m /= 5;
         }
       }
       //判断2和5的个数哪一个更少，得出有多少对2和5
       int ret = twoCount < fiveCount ? twoCount: fiveCount;
       System.out.println(ret);
       scan.close();
    }
}

题目来自：

乘积尾零 - 蓝桥云课 (lanqiao.cn)