题解 | #牛牛小数点#

题目大意

设f(x)函数是x在小数后第几位开始循环（如果不是循环小数即为0），如

现在给出l,r，让你求

解题思路

不难发现，对除数质因数分解，如果存在非2非5的数，那么就是循环的

而每出现一个2或5就会让循环开始的位置往后一位，同时出现则只计算一次，所以总贡献就是

所以只需枚举2和5的个数，然后容斥减去还有2,5没计算的情况和没有别的因数的情况，就是当前方案的数量，再乘上该方案的贡献，最后求和即可

（这里推荐一个更为详细且带有证明的题解，作者QuantAsk orz，题解：https://quant-ask.blog.csdn.net/article/details/120467008 ）

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define wyc 998244353
using namespace std;
int T;
ll l,r,k,w,now,sum,ans,num[60][60];
int main()
{
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld",&l,&r);
        l--;
        memset(num,0,sizeof(num));
        ans=0;
        for(int i=50;i>=0;--i){
            k=1ll<<i;
            if(k>r)continue;
            w=0;
            now=1;
            while(k*now*5<=r)now*=5,w++;//最大可以多少个
            for(int j=w;j>=0;--j){
                num[i][j]=r/(k*now)-l/(k*now);//数量
                sum=num[i][j]-num[i+1][j]-num[i][j+1]+num[i+1][j+1];//容斥
                if(r/(k*now)&&!(l/(k*now)))sum--;//l~r中没有别的因数的
                ans=(ans+sum%wyc*(max(i,j)+1)%wyc)%wyc;
                now/=5;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}