题解 P6583 【回首过去】

syksykCCC · 2020-06-03 00:37:54 · 题解

zrm 哥哥自己不写 sol 做 ppt 差评 /kel

好，那么官方题解只能我来写了 /kk

十进制有限小数

什么样子的分数可以表示为十进制有限小数？

约分后，分母只含 2, 5 两种因子的分数可以。

感性证明：

写成十进制有限小数的充要条件显然是分数可以通分为 \frac{a}{100\dots} 的形式，也就是对于一个整数左移小数点。

而形如 10^x 的数必然 =2^x\times 5^x，所以，分母只含 2, 5 两个因子即可。

子任务 1：n \le 10^3

做法 1

显然，枚举 p，枚举 q，暴力约分，判断 q 约分后是不是只含 2, 5 两种因子是可行的。

枚举的时间复杂度为 O(n^2)，约分的时间复杂度为 O(\log n)，判断分母的时间复杂度也为 O(\log n)，后面两者并列，所以，时间复杂度为 O(n^2 log n)。

至此，你还没有当年的小 Z 厉害（

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            int p = i, q = j;
            int g = __gcd(p, q);
            p /= g; q /= g;
            while(q % 2 == 0) q /= 2;
            while(q % 5 == 0) q /= 5;
            if(q == 1) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

做法 2

把分数分解一下，可以写为以下的形式：

被极短的 O(n \log n) 切了，长见识了 qwq

做法 1

观察上一个做法，发现不知道最后一重循环在干啥 /发抖

也就是说，枚举完一组 a 和 c 后，它对答案的贡献就是分子所能取的数量，即 [1, \lfloor\frac{n}{c} \rfloor]，直接加上这个贡献就好了。

那么省掉了一重循环，因为分母的枚举是 n 个不重不漏，时间复杂度 O(n)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, x[100000], cnt, ans;
signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i *= 2)
        for(int j = i; j <= n; j *= 5)
            x[++cnt] = j;
    sort(x + 1, x + cnt + 1);
    for(int i = 1; i <= cnt; i++)
    {
        int a = x[i];
        for(int b = 1; a * b <= n; b++)
        {
            if(b % 2 == 0 || b % 5 == 0) continue;
            ans += n / b;
        }
    }
    cout << ans << endl;
    return 0;
}

做法 2

想要继续优化，发现很难了，回到 O(n^2 ) 的做法，能不能通过转换顺序来达到优化时间的目的呢？

尝试先枚举 c，那么，b 的取值依然是 [1, \lfloor\frac{n}{c} \rfloor] 的任何数，而 a 的取值就变为了 [1, \lfloor\frac{n}{c} \rfloor] 中任何只含 2, 5 两种因子的数，发现，a 的取值的个数随着 c 的增大而单调减小，所以可以在总共 O(n) 的时间中计算，也就是，对于每个 c，记合法的 a 的个数为 d，则它对答案的贡献为 d \times \lfloor\frac{n}{c} \rfloor。

时间复杂度依然是 O(n)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, x[100000], cnt, ans;
signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i *= 2)
        for(int j = i; j <= n; j *= 5)
            x[++cnt] = j;
    sort(x + 1, x + cnt + 1);
    int a = cnt;
    for(int b = 1; b <= n; b++) 
    {
        if(b % 2 == 0 || b % 5 == 0) continue; 
        while(a && x[a] > n / b) a--;
        ans += a * (n / b);
    }
    cout << ans << endl;
    return 0;
}

子任务 3：n \le 10^{12}

不妨把 d 写的更直接一点，换成 f(x)，表示 [1, x] 中只含 2, 5 两个因子的数的个数。前面那个式子等价于：

发现，这个是一种经典的整除分块形式，直接整除分块，可以把时间复杂度加速到 O(\sqrt{n})。

真的这么简单么？

别忘了，c 的取值并不是 [1, n] 当中的每一个数，而是不含 2, 5 因子的数。

之前枚举的是 c，所以可以直接判断 c \bmod 2 和 c \bmod 5 是不是为 0，但现在我们要整段的处理 c，怎么办呢？

先忽略这个限制，把 c 的取值范围当作 [1, n] 当中的每一个数处理。比如 c\in[l, r] 时贡献相同，就可以通过容斥计算出 [l,r ] 中实际的合法的 c 的个数。