星际跃迁的稳定信标

题意

给一个正整数 $N$ ，找到最大的正整数 $x$ （ $x \le N$ ）满足：

$x$ 的各位数字从高位到低位非递减（称为"和谐频率"），例如 $1223$ 合法， $1232$ 不合法。
$x$ 的各位数字之和是质数。

如果不存在这样的 $x$ ，输出 $-1$ 。

思路

问题拆解

这道题有两个约束：非递减数字 + 数字和为质数。直接从 $N$ 往下暴力枚举所有整数肯定不行—— $N$ 可能达到 $10^{10}$ 量级。

换个角度想：如果我们已经知道数字和 $s$ 是某个质数，能不能快速找出数字和恰好为 $s$ 的、不超过 $N$ 的最大非递减数？

枚举质数目标和

$N$ 最多 $n$ 位，数字和最大 $9n$ （全 $9$ 的情况）。对于 $n \le 10$ ，数字和不超过 $90$ ，质数只有二三十个。对每个质数 $s$ ，我们去找满足条件的最大数。最后在所有候选答案中取最大值就行。

贪心构造：怎么找最大的非递减数？

对于固定的目标数字和 $s$ ，我们从高位到低位逐位构造：

每一位尽量选最大的数字（这样整个数才最大）
约束一：当前数字 $\ge$ 上一位数字（非递减）
约束二：如果还"顶着" $N$ 的上界（tight），当前数字 $\le N$ 对应位的数字
约束三：剩余位数能凑出剩余的目标和。假设当前选了 $d$ ，后面还有 $k$ 位，每位至少 $d$ （非递减），至多 $9$ ，所以剩余和 $r$ 需要满足 $k \cdot d \le r \le 9k$ 。

从大到小试每个合法的 $d$ ，第一个满足所有约束的就是当前位的最优选择。如果这一位选了比 $N$ 对应位更小的数字，后面就不再受 $N$ 的限制（解除 tight），可以尽情往大了选。

这里有个细节：如果在 tight 状态下走到某一位发现无路可走（比如 $N$ 当前位是 $0$ ，但前一位已经选了 $3$ ），就需要回溯——回到上一位选一个更小的数字。用递归实现最自然。

复杂度分析

质数个数 $O(n)$ 级别，每个质数做一次 DFS，DFS 的每一层最多试 $10$ 个数字，深度为 $n$ 。回溯剪枝后实际搜索量很小。

总时间复杂度 $O(n^2 \times 10)$ ，对于 $n \le 10$ 完全没有压力。

代码

C++
Java
Python3
JavaScript

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

bool isPrime(int n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;
}

string N;
int n;

string solve(int len, int pos, int lastD, bool tight, int rem, string& cur) {
    if (pos == len) return rem == 0 ? cur : "";
    int remaining = len - pos - 1;
    int lo = pos == 0 ? 1 : lastD;
    int hi = (tight && len == n) ? (N[pos] - '0') : 9;
    for (int d = hi; d >= lo; d--) {
        int r = rem - d;
        if (r < 0) continue;
        if (r < (long long)remaining * d) continue;
        if (r > (long long)remaining * 9) continue;
        cur[pos] = '0' + d;
        bool nt = tight && (len == n) && (d == N[pos] - '0');
        string res = solve(len, pos + 1, d, nt, r, cur);
        if (!res.empty()) return res;
    }
    return "";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    n = N.size();
    string best;
    for (int t = 2; t <= 9 * n; t++) {
        if (!isPrime(t)) continue;
        for (int len = n; len >= 1; len--) {
            if (t > 9 * len) break;
            string cur(len, '0');
            string res = solve(len, 0, 0, len == n, t, cur);
            if (!res.empty()) {
                if (best.empty() || res.size() > best.size() ||
                    (res.size() == best.size() && res > best))
                    best = res;
                break;
            }
        }
    }
    cout << (best.empty() ? "-1" : best) << "\n";
}

import java.util.Scanner;

public class Main {
    static String N;
    static int n;
    static char[] current;

    static boolean isPrime(int x) {
        if (x < 2) return false;
        if (x < 4) return true;
        if (x % 2 == 0 || x % 3 == 0) return false;
        for (int i = 5; i * i <= x; i += 6)
            if (x % i == 0 || x % (i + 2) == 0) return false;
        return true;
    }

    static boolean solve(int len, int pos, int lastD, boolean tight, int rem) {
        if (pos == len) return rem == 0;
        int remaining = len - pos - 1;
        int lo = pos == 0 ? 1 : lastD;
        int hi = (tight && len == n) ? (N.charAt(pos) - '0') : 9;
        for (int d = hi; d >= lo; d--) {
            int r = rem - d;
            if (r < 0) continue;
            if (r < (long) remaining * d) continue;
            if (r > (long) remaining * 9) continue;
            current[pos] = (char) ('0' + d);
            boolean nt = tight && (len == n) && (d == N.charAt(pos) - '0');
            if (solve(len, pos + 1, d, nt, r)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.next();
        n = N.length();
        String best = "";
        for (int t = 2; t <= 9 * n; t++) {
            if (!isPrime(t)) continue;
            for (int len = n; len >= 1; len--) {
                if (t > 9 * len) break;
                current = new char[len];
                if (solve(len, 0, 0, len == n, t)) {
                    String res = new String(current);
                    if (best.isEmpty() || res.length() > best.length() ||
                        (res.length() == best.length() && res.compareTo(best) > 0))
                        best = res;
                    break;
                }
            }
        }
        System.out.println(best.isEmpty() ? "-1" : best);
    }
}

import sys
sys.setrecursionlimit(10000)

def is_prime(x):
    if x < 2: return False
    if x < 4: return True
    if x % 2 == 0 or x % 3 == 0: return False
    i = 5
    while i * i <= x:
        if x % i == 0 or x % (i + 2) == 0: return False
        i += 6
    return True

def solve():
    N = input().strip()
    n = len(N)
    best = ""

    for target in range(2, 9 * n + 1):
        if not is_prime(target):
            continue
        for length in range(n, 0, -1):
            if target > 9 * length:
                break
            current = ['0'] * length
            tight = (length == n)

            def dfs(pos, lastD, tight_flag, rem):
                if pos == length:
                    return rem == 0
                remaining = length - pos - 1
                lo = 1 if pos == 0 else lastD
                hi = int(N[pos]) if (tight_flag and length == n) else 9
                for d in range(hi, lo - 1, -1):
                    r = rem - d
                    if r < 0: continue
                    if r < remaining * d: continue
                    if r > remaining * 9: continue
                    current[pos] = str(d)
                    nt = tight_flag and (length == n) and (d == int(N[pos]))
                    if dfs(pos + 1, d, nt, r):
                        return True
                return False

            if dfs(0, 0, tight, target):
                res = ''.join(current)
                if not best or len(res) > len(best) or \
                   (len(res) == len(best) and res > best):
                    best = res
                break

    print(best if best else -1)

solve()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

rl.on('line', (line) => {
    const N = line.trim();
    const n = N.length;

    function isPrime(x) {
        if (x < 2) return false;
        if (x < 4) return true;
        if (x % 2 === 0 || x % 3 === 0) return false;
        for (let i = 5; i * i <= x; i += 6)
            if (x % i === 0 || x % (i + 2) === 0) return false;
        return true;
    }

    let best = "";

    for (let target = 2; target <= 9 * n; target++) {
        if (!isPrime(target)) continue;
        for (let len = n; len >= 1; len--) {
            if (target > 9 * len) break;
            const current = new Array(len).fill('0');

            function dfs(pos, lastD, tight, rem) {
                if (pos === len) return rem === 0;
                const remaining = len - pos - 1;
                const lo = pos === 0 ? 1 : lastD;
                const hi = (tight && len === n) ? parseInt(N[pos]) : 9;
                for (let d = hi; d >= lo; d--) {
                    const r = rem - d;
                    if (r < 0) continue;
                    if (r < remaining * d) continue;
                    if (r > remaining * 9) continue;
                    current[pos] = String(d);
                    const nt = tight && (len === n) && (d === parseInt(N[pos]));
                    if (dfs(pos + 1, d, nt, r)) return true;
                }
                return false;
            }

            if (dfs(0, 0, len === n, target)) {
                const res = current.join('');
                if (!best || res.length > best.length ||
                    (res.length === best.length && res > best))
                    best = res;
                break;
            }
        }
    }

    console.log(best || "-1");
    rl.close();
});