P9309 题解

此题问 \(\operatorname{lcm}(a\sim b)\) 的后导 \(0\) 个数。
考虑 \(\operatorname{lcm}\) 相当于对唯一分解中的素数的指数取 \(\max\)，此题等价于：

定义 \(\operatorname{g}(x,y,z)\) 在 \([a,b]\) 的所有整数中，分解出 \(z\) 的最高次幂是多少，那么 \(ans=\min(\operatorname{g}(a,b,2),\operatorname{g}(a,b,5))\)。

下面转化为求 \(\operatorname{g}\)。其实这也显然，我们只需要对 \(a,b\) 持续的除以 \(z\)，直到 \(a=b\)，这说明 \(a,b\) 在 \(z\) 的幂的“同一倍数”里。再考虑一下边界问题，我们不难得到下面的代码：

#include<bits/stdc++.h>
using namespace std;
long long get(long long x,long long y,int a){
    int cnt=-1;
    while(x!=y){
        cnt++;
        x/=a,y/=a;
    }
    return cnt;
}
int main() {
    long long a,b;
    cin>>a>>b;
    a--;
    cout<<min(get(a,b,2),get(a,b,5));
}

即为本题答案。