P6583 回首过去 题解

题目传送门

好题。

更新（2023-12-05）：把代码和 $\LaTeX$ 改得更好看了。

题意简述

给定正整数 $n$，求出有序整数对 $(x, y)$ 的个数，满足 $1 \le x,y \le n$ 且 $\dfrac x y$ 可以表示为十进制有限小数。

$1 \le n \le 10^{12}$。

前置知识

• 数论分块

解法

Subtask 1 $O(n^2 \log n)$

根据小学奥数知识可知，一个分数在十进制下为有限小数，当且仅当约分后的分母的质因数分解只有 $2$ 和 $5$。

暴力验证每一个范围内的分数。

Subtask 2 $O(n \log n)$

根据上文的结论，设 $y = 2^a 5^b d, x = \lambda d$。其中 $d$ 与 $2$ 和 $5$ 互质。

首先需要知道这样一件事：

记 $f(x)$ 为 $[1,x]$ 中有几个数是 $2^a 5^b$ 的形式，其中 $a,b$ 可以等于 $0$。

我们可以在 $O(\log n)$ 的时间内快速计算 $f(n)$：

在代码中 $\log_5 x$ 可以用 $\dfrac {\ln x}{\ln 5}$ 来计算。

ll f(ll x) {
    ll ret = 0;
    for (ll i = 0; (1ll << i) <= x; i++)
        ret += ll(log(x >> i) / log(5)) + 1;
    return ret;
}

记 $val = \left\lfloor \dfrac n d \right\rfloor$。

所以我们可以枚举 $d$，那么 $y$ 的个数即为 $f(val)$，$x$ 的个数即为 $val$。

即答案为：

        ll ans = 0;
        for (ll d = 1; d <= n; d++) {
            if (d % 2 == 0 || d % 5 == 0)
                continue;
            ll val = n / d;
            ans += val * f(val);
        }
        cout << ans << '\n';

Subtask 3 $O(\sqrt n \log n)$

注意到 $val$ 的形式长得很像数论分块，考虑使用数论分块将其加速到根号级别。

在 $val$ 为定值的区间内，$f(val) \times val$ 为一定值，但是 $[2 \nmid d][5 \nmid d]$ 会变。

也就是说，我们需要知道在一个区间 $[l,r]$ 内有几个数满足 $2 \nmid d$ 且 $5 \nmid d$。

考虑前缀和，设 $g(x)$ 为 $[1,x]$ 内有几个数满足 $2 \nmid d$ 且 $5 \nmid d$。

根据容斥，有 $g(x) = x - \left\lfloor \dfrac x 2 \right\rfloor - \left\lfloor \dfrac x 5 \right\rfloor + \left\lfloor \dfrac x {10} \right\rfloor$。

区间 $[l,r]$ 内满足 $2 \nmid d$ 且 $5 \nmid d$ 的数的个数则为 $g(r) - g(l-1)$。

此时可以使用数论分块了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll f(ll x) {
    ll ret = 0;
    for (ll i = 0; (1ll << i) <= x; i++)
        ret += ll(log(x >> i) / log(5)) + 1;
    return ret;
}

ll g(ll x) {
    return x - x / 2 - x / 5 + x / 10;
}

int main() { ios::sync_with_stdio(0); cin.tie(0);
    ll n; cin >> n;
    ll ans = 0;
    for (ll l = 1, r; l <= n; l = r + 1) {
        ll val = n / l;
        r = n / val;
        ans += (g(r) - g(l-1)) * val * f(val);
    }
    cout << ans << '\n';
    return 0;
}