G5021 [GESP202603 五级] 有限不循环小数 题解

知识点：枚举、质因数、乘法生成。

解题思路

最简分母只含质因子2和5时，倒数才是有限小数。枚举2^a乘5^b落在[l,r]的数并计数。

为什么正确

十进制有限小数的分母整除某个10的幂，恰等价于只含2和5；唯一分解保证每个指数对对应唯一数字。

易错点

指数可以为0，所以包括1；循环中从2的幂a开始再连乘5。

复杂度

时间O(log r·log r)，即O(log²r)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long l,r;
    cin>>l>>r;
    int ans=0;
    for(long long a=1;a<=r;a*=2)for(long long b=a;b<=r;b*=5)ans+=b>=l;
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。