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

jellye · 2026-10-19 16:46:08 · 题解

题意

给定 a，l，r，求满足 x \in [l, r] 且 \frac{a}{x} 为有限小数的 x 的个数。

思路

我们从 \frac{a}{x} 为有限小数这个条件入手。如果 \frac{p}{q} 为有限小数且 p、q 互质，那么一定存在非负整数 x、y 使得 q = {2}^{x} \times {5}^{y}，即 q 只可能有 2、5 两个质因数。

这里简单证明一下：因为 \frac{p}{q} 为有限小数，所以一定存在非负整数 x 使得 \frac{p}{q} \times {10}^{x} 为整数，即 p \times {10}^{x} 为 q 的倍数。由于 p、q 互质，就有 {10}^{x} 为 q 的倍数。因为 {10}^{x} = {2}^{x} \times {5}^{x}，所以 q 只可能有 2、5 两个质因数。

回到题目，由于 a 与 x 并不互质，我们需要约分。具体地，在输入之后将 a 中 2 和 5 的质因数全部除掉。将处理后的 a 写作 a'，这时，x 满足条件当且仅当 x = b \times {2}^{p} \times {5}^{q} 且 x \in [l, r]，其中 b 为 a' 的因数，p、q 为非负整数。

证明非常简单：分子上 a' 把 b 消掉了，此时 \frac{a'}{b} 与 {2}^{p} \times {5}^{q} 互质，因此原式为有限小数。

因此我们枚举 a' 的因数 b，然后枚举 p、q，得到合法的 x。由于质因数分解是唯一的，这样枚举可以做到不重不漏。这里有一个常用的枚举因数的技巧：只枚举 \le \sqrt {a'} 的 b，另一个因数即为 \frac{a'}{b}。但是需要判断 b = \sqrt {a'} 的情况。

记得开 long long。

复杂度分析

时间复杂度

枚举 b 为 O(\sqrt {a'})，枚举 p、q 为 O(\log_{2} r \times \log_{5} r)，后者由于 r \le {10}^{15} 大约为 1000，总复杂度为 O(\sqrt {a'} \times \log_{2} r \times \log_{5} r)，可以通过。

空间复杂度

只需定义若干单独变量，复杂度 O(1)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,l,r,ans;
signed main()
{
    cin>>a>>l>>r;
    while(a%2==0) a/=2;
    while(a%5==0) a/=5;
    for(int b=1;b*b<=a;b++)
        if(a%b==0)
        {
            for(int i=b;i<=r;i*=2)
                for(int j=i;j<=r;j*=5)
                    if(l<=j) ans++;
            if(b*b!=a)
                for(int i=a/b;i<=r;i*=2)
                    for(int j=i;j<=r;j*=5)
                        if(l<=j) ans++;
        }
    cout<<ans;
}