P9309 [EGOI2021] Number of Zeros题解

模拟赛时以为是进位制的题目，结果还做出来了。

此题解解法与其它相似，但观察的角度不同（作者的脑回路不同）。

此题问 \(a\sim b\) 的最小公倍数中后导 \(0\)的个数，即求其中 \(2\) 和 \(5\) 个数的最小值。

分别计算即可，想到进位制，以 \(a=10\) , \(b=12\) 时 \(2\) 的个数为例：

1001(9)
1010(10)
1011(11)
1100(12)

观察发现从 \(9\) 到 \(12\) 时， 变化的最高位是 \(2^2\) ，说明 \(10\sim 12\) 一定有 \(2^2\) 的倍数。

若 \(a-1\) 到 \(b\) 中某一位不变，则其它位一定有变化，不影响答案，求变化的最高位即可。

$ 5 $ 的个数同理。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b;
int p[100],q[100];
int main(){
    scanf("%lld%lld",&a,&b);
    ll t1=a-1,t2=b,t3=a-1,t4=b;
    int tot1=0,tot2=0,tot3=0,tot4=0,ans2=0,ans5=0;
    while(t1){
        p[++tot1]=t1&1;
        t1>>=1;
    }
    while(t2){
        if((t2&1)!=p[++tot2]){
            ans2=tot2-1;
        }
        t2>>=1;
    }
    while(t3){
        q[++tot3]=t3%5;
        t3/=5;
    }
    while(t4){
        if(t4%5!=q[++tot4]){
            ans5=tot4-1;
        }
        t4/=5;
    }
    printf("%d",min(ans2,ans5));
    return 0;
}