P10404 「XSOI-R1」原神数 题解

· · 题解

一篇题解需要一张头图。

容易发现超过十位的数都不是原神数，因为只有十个数字，不可能保证十一个位置互不相同。
同时恰好十位的数也不可能是原神数，因为数位互不相同的十位数的数位和为 45，被 3 整除，一定是 3 的倍数。
于是把原神数的范围缩小到 [1, 10^9)。

显然不能在回答询问时处理答案，考虑预处理出所有原神数并二分回答询问。

考虑先满足数位互不相同的限制，DFS 搜索出所有数位互不相同的数并判断其是否是质数。
可以计算出，需要判断 \binom 9 8 1! + \binom 9 7 2! + \binom 9 6 3! + \cdots + \binom 9 9 9! = 986409 次。
只需要寻找一个快速的质数判断方法，回收头图：Miller–Rabin 被卡得飞起。
考虑分治：使用线性筛判断不超过阈值的数，超过阈值的数通过枚举线性筛得到的素数进行判断。
取阈值为 2 \cdot 10^6 可以通过本题。

正确性证明 定理：对于一个合数 x，其最小质因子不超过 \sqrt x。在 [2, 2 \cdot 10^6) 的素数内一定可以找到待判断的数（如果是合数）的最小质因子。正确性得证。

时间复杂度证明 设待判断的数为 x，阈值为 B。如果 x \leqslant B，可以 O(1) 判断；如果 x > B，根据前述定理，会枚举 \pi(\lfloor \sqrt x \rfloor) \sim \frac {\sqrt x} {\ln(\sqrt x)} 个质数。勉强可以通过。

因为有些卡常所以比较难看的代码。

#include <algorithm>
#include <iostream>
#include <vector>

typedef long long ll;

using namespace std;

const int lim = 2e6;

int q;
ll l, r;
bool isp[lim + 5];
int pr[lim + 5], pi;
static inline bool chk(int x) {
    if (x <= lim)
        return !isp[x];
    for (int i = 1; pr[i] * pr[i] <= x; ++i)
        if (x % pr[i] == 0)
            return false;
    return true;
}

bool vis[12];
vector<int> gen;
static inline void dfs(int u, int val, int aim) {
    if (u == aim) {
        if (chk(val))
            gen.push_back(val);
        return;
    }
    for (int i = 0; i <= 9; ++i) {
        if (u == 0 && i == 0)
            continue;
        if (vis[i])
            continue;
        vis[i] = 1;
        dfs(u + 1, val * 10 + i, aim);
        vis[i] = 0;
    }
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
#endif
    isp[0] = isp[1] = 1;
    for (int i = 2; i <= lim; ++i) {
        if (!isp[i])
            pr[++pi] = i;
        for (int j = 1; j <= pi && i * pr[j] <= lim; ++j) {
            isp[i * pr[j]] = 1;
            if (i % pr[j] == 0)
                break;
        }
    }
    for (int i = 1; i <= 9; ++i)
        dfs(0, 0, i);
    scanf("%d", &q);
    while (q--) {
        scanf("%lld %lld", &l, &r);
        printf("%d\n", (int)(upper_bound(gen.begin(), gen.end(), r) - lower_bound(gen.begin(), gen.end(), l)));
    }
    return 0;
}