c++ - C++:数组乘法中的尾随零

给定数组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[].

我该如何改善？还是有其他不同的方法可以更快地计算出来。请帮帮我。

最佳答案

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

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，那么它们将不贡献任何其他零，反之亦然反之亦然。因此，尾随零的数目等于两个计数中的较小者。

关于c++ - C++:数组乘法中的尾随零，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40007445/