题解：P17712 Red Face 统计数（decimal）

· · 题解

oi，我又来水题解啦（QwQ）！

首先有限小数肯定是指将这个分数约分后分母能拆成若干个 2 和 5 的积。

所以剩下的就是模拟了，一开始将 a 的因数 2 和 5 去掉（去重），然后枚举处理后的 a 的所有因数，对于每一个因数，枚举它乘上若干个 2，5 的积在区间 [l,r] 之间的数的个数。

复杂度 O(\sqrt{a}+d(a)log^2r)，d(a) 代表 a 除去 2 和 5 之后的因数数量。

::::info[枚举在区间内个数的函数]{open}

ll cnt(ll t,ll &l,ll &r)
{
    ll res=0;
    //枚举 2 的次方
    for(ll i=1;i*t<=r;i<<=1)
    {
        //枚举 5 的次方
        for(ll j=1;i*j*t<=r;j*=5)
        {
            //满足条件
            if(i*j*t>=l) res++;
        }
    }
    return res;
}

::::

::::info[主函数]{open}

ll a,l,r;
ll ans=0;
cin >> a >> l >> r;
for(ll i=1; i<=a/i; ++i)
//枚举因数
{
    if(a%i==0)
    {
        //防止重复
        if(i*i!=a)ans+=cnt(a/i,l,r);
        ans+=cnt(i,l,r);
    }
}
//收工！
cout << ans;

::::