P9309 [EGOI2021] Number of Zeros / 零的个数

· · 题解

题意理解

给出两个正整数 a 和 b。 想要让礼物可以被 x \in \{a,a+1,…,b\} 个孩子平分。 求答案的后导零个数。

思路阐述

首先想要让礼物可以被 x \in \{a,a+1,…,b\} 个孩子平分即为求这个集的最小公倍数，但是数据范围很大，直接求显然会超时。 题目中要求的是后导零的个数，即答案中有几个 10 作为因子，而 10 又可以分解为 2\times 5，所以后导零的个数即为答案中质因子 2 的个数和 5 的个数的最小值。 接下来便是求范围内含因子 2 最多的数有几个 2 因子和含因子 5 最多的数有几个 5 因子。

代码呈现

#include <bits/stdc++.h>
using namespace std;

#define int unsigned long long

int a,b;

int f(int x,int y,int k){//在范围x~y中因子k的最大个数
    int cnt=0;
    while (x!=y){
        x/=k;
        y/=k;//不断除k，增加答案
        cnt++;
    }
    return cnt-1;//注意答案最后要减一
}

signed main(){

    scanf("%lld%lld",&a,&b);
    a--;//a在范围内，下界要低一个
    printf("%lld",min(f(a,b,2),f(a,b,5)));
    return 0;

}

希望可以帮到各位大佬。