题面描述

这类题型有几个比较明显的特征：

  1. 通常询问的是 ≤n\le n 内满足某个条件的数有多少个
  2. 通常数据范围很大，如 n≤1018n\le 10^{18}

解法一：素因子分解法

这一种方法的视角下，条件通常可以在素因子分解后，转化成指数上的约束，大大减少了可能的数得到范围。

【例】Number Reduction

考虑一个数 xx，如果 xx 的十进制表示中含有 kk (2≤k≤92\le k\le 9) 且 k∣xk|x，则将 x←xkx\gets \frac{x}{k}.

如果 xx 可以经过以上任意次操作变成 11，则 xx 是 Good 的。给定一个整数 n≤1018n\le 10^{18}，问有多少个数 ≤n\le n 是 Good 的？

根据题面，显然我们每次只能除以 2∼92\sim 9，既然最后可以变成 11，这就说明 xx 只能含有因子 2,3,5,72,3,5,7，即

x=2a3b5c7d x=2^a3^b5^c7^d

那么 ≤1018\le 10^{18} 有多少数满足这样的形式呢？答案是 log⁡2(1e18)×log⁡3(1e18)×log⁡5(1e18)×log⁡7(1e18)≈1.2×106\log_2(1e18)\times\log_3(1e18)\times\log_5(1e18)\times\log_7(1e18)\approx 1.2\times 10^6. 可以看到量级最大大概只有 10610^6.

确定了数不多后，我们考虑把所有这样的数都提取出来，然后检查数位和整除的条件. 既然最终可以变成 11，这样一个变化的过程即

a0=1→×m0a1→×m1a2→×m2…→×mkak+1 a_0=1\underset{\times m_0}{\to}a_1\underset{\times m_1}{\to}a_2\underset{\times m_2}{\to}\dots\underset{\times m_k}{\to}a_{k+1}

这里 mi∈[2,9]m_i\in [2,9]，所以其实相当于在有向无环图，以 11 为起点能到达的所有点。我们只需要对每一个 x=2a3b5c7dx=2^a3^b5^c7^d，枚举数位并判断整除，然后在图上添加有向边，最后从 11 开始跑 DFS 即可。

【时间复杂度】枚举 2a3b5c7d2^a3^b5^c7^d 需要 O(log⁡4n)O(\log^4 n) 的时间，再算上枚举数字和其数位，需要 O(log⁡5n)O(\log^5 n).

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <algorithm>
#include <cmath>
#include <iostream>
#include <unordered_map>
#include <vector>
using i64       = long long;
using vi        = std::vector<int>;
constexpr int N = 1e7 + 5;

vi G[N];
i64 n;
std::vector<i64> v;
std::unordered_map<i64, int> mp;
int mark[10];

i64 get_num(i64 a, i64 b, i64 c, i64 d) {
    return std::pow(2ll, a) * std::pow(3ll, b) * std::pow(5ll, c) * std::pow(7ll, d);
}

int main() {
    std::cin >> n;

    for (i64 a = 1; a <= n; a *= 2) {
        for (i64 b = 1; b <= n; b *= 3) {
            for (i64 c = 1; c <= n; c *= 5) {
                for (i64 d = 1; d <= n; d *= 7) {
                    i64 x = a * b * c * d;
                    if (x <= n) v.push_back(x);
                }
            }
        }
    }

    for (int i = 0; i < v.size(); i++) mp[v[i]] = i;
    for (int i = 0; i < 10; i++) mark[i] = -1;

    for (int i = 0; i < v.size(); i++) {
        i64 x = v[i];
        while (x > 0) {
            mark[x % 10] = i;
            x /= 10;
        }

        for (int j = 2; j <= 9; j++) {
            if (mark[j] != i || v[i] % j != 0 || !mp.count(v[i] / j)) continue;
            G[mp[v[i] / j]].push_back(mp[v[i]]);
        }
    }

    int ans = 0;
    vi vis(v.size(), false);
    auto dfs = [&](auto F, int u) -> void {
        vis[u] = true;
        ans++;
        for (int v : G[u])
            if (!vis[v]) F(F, v);
    };

    dfs(dfs, mp[1]);
    std::cout << ans << std::endl;
}

解法二：数位 DP

算是数数字的正统方法。记忆化搜索的写法比迭代的写法更简单易懂。