自动搬运

查看原文

来自洛谷，原作者为

	Red0rangE .

搬运于2025-08-24 22:47:13，当前版本为作者最后更新于2023-05-03 10:26:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意理解

给出两个正整数 $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;
    
}

希望可以帮到各位大佬。