C++ : Trailing zeroes in array multiplication

Question

给定一个数组 A，我必须将数组的所有元素相乘。由于数字可以达到 10^9 ，我必须找到产品的尾随零。我做了以下事情:

int ans= 0; // to count no of trailing zeroes 
 for(long int i =0; i<n ; i++) // n can be very large(upto 10^5)
 { 
    long long int p=1;
   p=p*a[i];
  while (p2℅10 ==0)
   { ans++;
     p=p/10;
    }
 }

计算2个数的函数如下。我用 5 代替 2 来计算 5 的个数。

Int nm2(long long a)
{
  Int b=0;
  while(a℅2==0){
    a=a/2;
     b++;
    }
  return b;
  }

Int p2=0,p5=0;
For(long long i=L;i<R;i++)
 { 
   p2 += nm2(a[i]);
   p5 += nm5 (a[i]);
  }
 Int ans += min(p2,p5); // storing no of zeroes every time I multiply elements of array from Index L to Index R of array a[].

我该如何改进它？或者有没有其他不同的方法可以更快地计算它。请帮帮我。

Answer 1

这更多的是关于数论而不是关于除法的细节。这是我会做的

int fives = 0;
int twos = 0;

for (int i=0; i<n; i++) {
    fives += countFives(a[i]);
    twos += countTwos(a[i]);
}

int trailingZeros = fives > twos ?  twos : fives; 

countTwos 和 countFives 这两个函数非常简单，分别计算给定输入值的因子 2 和 5 的个数。

计算尾随零数的行是基于这样一个事实，即每个尾随零必须恰好是 2 的一个因数和 5 的一个因数。如果 2 多于 5，它们将不会贡献任何额外的零，反之亦然。所以尾随零的数量等于两个计数中较小的一个。