题解 | #星际跃迁的稳定信标#

题目链接

星际跃迁的稳定信标

题目描述

给定一个正整数 $N$ ，代表引擎能承受的最大频率。我们需要找到不大于 $N$ 的、值最大的 和谐频率 $F$ 。和谐频率 需要满足两个条件：

其各位数字从高位到低位是一个非递减序列（例如， $123$ 、 $447$ 都是和谐的）。
其“能量签名”（各位数字之和）必须为一个质数。

如果不存在这样的频率，则返回 $0$ 。

解题思路

这是一个结合了数位搜索和质数判断的题目。由于输入 $N$ 的范围可达 $10^{18}$ ，直接从 $N$ 向下遍历并检查每个数字的属性会超时。

我们可以注意到，满足“和谐”条件（即各位数字非递减）的数字是相对稀疏的。因此，一个更高效的策略是主动构造所有满足条件的和谐数，而不是检查每一个数。我们可以使用深度优先搜索（DFS）来生成所有不超过 $N$ 的和谐数。

具体思路如下：

生成和谐数：我们定义一个递归函数 dfs(current_num, last_digit, digit_sum)，用于生成和谐数。
- $current\_num$ ：当前已经构建的和谐数。
- $last\_digit$ ：添加到 $current\_num$ 的最后一位数字。为了满足非递减的要求，下一个要添加的数字必须大于或等于 $last\_digit$ 。
- $digit\_sum$ ： $current\_num$ 的各位数字之和。
搜索过程：
- 搜索从 $1$ 到 $9$ 的个位数开始。
- 在每一步 dfs 中，我们尝试在 $current\_num$ 的末尾追加一个新数字 $d$ （其中 $d \ge last\_digit$ ），形成一个新的、更长的和谐数，然后继续递归。
- 剪枝：如果任何时候生成的 $current\_num$ 超过了输入的上限 $N$ ，就停止向更深的层次搜索，因为任何基于它的后续数字都将更大。
检查条件并更新答案：
- 每生成一个有效的和谐数（即不超过 $N$ ），我们检查其 $digit\_sum$ 是否为质数。
- 如果 $digit\_sum$ 是质数，我们就用这个和谐数更新全局的最大答案。
质数预处理：由于 $N$ 最大为 $10^{18}$ （最多18位），其最大可能的数位和是 $9 \cdot 18 = 162$ 。我们可以预先使用筛法（例如埃拉托斯特尼筛法）计算出 $162$ 以内所有的质数，以便在搜索中进行快速查询。

通过这种方式，我们只访问了所有不超过 $N$ 的和谐数，大大减少了计算量，从而可以在规定时间内找到答案。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <climits> // For LLONG_MAX

using namespace std;
using ll = long long;

ll N;
ll ans = 0;
bool found = false; // 标记是否找到解
vector<bool> is_prime;

// 埃拉托斯特尼筛法预处理质数
void sieve(int max_val) {
    is_prime.assign(max_val + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p <= max_val; p++) {
        if (is_prime[p]) {
            for (int i = p * p; i <= max_val; i += p)
                is_prime[i] = false;
        }
    }
}

// DFS生成和谐数
void dfs(ll current_num, int last_digit, int digit_sum) {
    if (current_num > N) {
        return;
    }

    if (is_prime[digit_sum]) {
        ans = max(ans, current_num);
        found = true;
    }

    for (int d = last_digit; d <= 9; ++d) {
        // 防止溢出
        if (current_num > LLONG_MAX / 10 || (current_num == LLONG_MAX / 10 && d > LLONG_MAX % 10)) {
            break;
        }
        ll next_num = current_num * 10 + d;
        
        dfs(next_num, d, digit_sum + d);
    }
}

int main() {
    cin >> N;
    
    // N最多18位，最大数位和为 9 * 18 = 162
    sieve(162); 
    
    // 从1到9的个位数开始搜索
    for (int d = 1; d <= 9; ++d) {
        dfs(d, d, d);
    }

    if (found) {
        cout << ans << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    static long N;
    static long ans = 0;
    static boolean found = false; // 标记是否找到解
    static boolean[] isPrime;

    // 埃拉托斯特尼筛法预处理质数
    static void sieve(int maxVal) {
        isPrime = new boolean[maxVal + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; p * p <= maxVal; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= maxVal; i += p)
                    isPrime[i] = false;
            }
        }
    }

    // DFS生成和谐数
    static void dfs(long currentNum, int lastDigit, int digitSum) {
        if (currentNum > N) {
            return;
        }

        if (isPrime[digitSum]) {
            ans = Math.max(ans, currentNum);
            found = true;
        }

        for (int d = lastDigit; d <= 9; d++) {
            // 防止溢出
            if (currentNum > Long.MAX_VALUE / 10 || (currentNum == Long.MAX_VALUE / 10 && d > Long.MAX_VALUE % 10)) {
                break;
            }
            long nextNum = currentNum * 10 + d;
            dfs(nextNum, d, digitSum + d);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextLong();
        
        // N最多18位，最大数位和为 9 * 18 = 162
        sieve(162);

        // 从1到9的个位数开始搜索
        for (int d = 1; d <= 9; d++) {
            dfs(d, d, d);
        }

        System.out.println(found ? ans : -1);
    }
}

import math

# 全局变量存储答案和输入
ans = 0
found = False # 标记是否找到解
n_val = 0
is_prime = []

# 埃拉托斯特尼筛法预处理质数
def sieve(max_val):
    global is_prime
    is_prime = [True] * (max_val + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(math.sqrt(max_val)) + 1):
        if is_prime[p]:
            for i in range(p * p, max_val + 1, p):
                is_prime[i] = False

# DFS生成和谐数
def dfs(current_num, last_digit, digit_sum):
    global ans, n_val, found
    
    if current_num > n_val:
        return

    if is_prime[digit_sum]:
        ans = max(ans, current_num)
        found = True

    for d in range(last_digit, 10):
        next_num = current_num * 10 + d
        dfs(next_num, d, digit_sum + d)

# 主逻辑
n_val = int(input())

# N最多18位，最大数位和为 9 * 18 = 162
sieve(162)

# 从1到9的个位数开始搜索
for d in range(1, 10):
    dfs(d, d, d)

print(ans if found else -1)

算法及复杂度

算法：深度优先搜索（DFS） + 筛法求质数。
时间复杂度：主要由DFS的搜索空间决定。设 $N$ 的位数为 $L$ （本题中 $L \le 18$ ），和谐数的数量级约为组合数 $\binom{9+L}{L}$ 。筛法的时间复杂度为 $\mathcal{O}(S \log \log S)$ ，其中 $S$ 为最大数位和（ $162$ ）。因此，总时间复杂度由DFS主导，约为 $\mathcal{O}(\binom{9+L}{L})$ 。
空间复杂度： $\mathcal{O}(L + S)$ ，为DFS的递归深度和存储质数表的空间。由于 $L$ 和 $S$ 都很小，空间复杂度可视为 $\mathcal{O}(1)$ 。