文章

乘积尾零(2018省赛)

乘积尾零.png

1 暴力求解,对得数的后位0记录后舍去, 前面数太大直接取余一个较大的数方便运算

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,x,i;
    long long sum=1;
    long long cnt=0;
    for(i=1;i<=100;i++){
        cin>>x;
        sum*=x;
        sum%=10000000;
        while(sum%10==0){
            cnt++;
            sum/=10;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

2 分解质因数法 每个0都是由2*5组成的,算出每个数的质因子的2和5的个数,然后总的2 和总的5算出来,取两数中较小的一个就是答案

#include<bits/stdc++.h>
using namespace std;
int s2=0;
int s5=0;
void cal(int x){
    while(x%2==0){
        x/=2;
        s2++;
    }
    while(x%5==0){
        x/=5;
        s5++;
    }
    return ;
}
int main()
{
    int x;
    for(int i=1;i<=100;i++){
        cin>>x;
        cal(x);
    }
    cout<<min(s2,s5)<<endl;
    return 0;
}

原题链接

https://www.lanqiao.cn/problems/612/learning/

License:  CC BY 4.0