解题思路

算法概述

1. 转成字符串处理
   将输入的正整数 $n$ 转为长度为 $L$ 的字符串 s。
2. 贪心+回溯构造
   从最高位到最低位逐位决定数字。对第 i 位，我们在合法范围内（若受上界约束则不超过 s[i]，否则不超过 9；且不小于前一位已定的数字）的候选数字中，从大到小尝试最优选择。
3. 可行性剪枝
   每选一个数字 d 之后，根据当前已选的数字和剩余位置，可算出可能的最小/最大剩余位数和：

   新和 newSum = sumSoFar + d
   剩余位数 rem = L−i−1
   最小可能总和 lo = newSum + d*rem
   最大可能总和 hi = newSum + 9*rem
   

   如果区间 [lo, hi] 中不存在质数，则跳过该 d。
4. 多长度尝试
   若在与 $n$ 同长度下无法找到解，则依次尝试长度 $L−1,L−2,…,1$，每次将上界字符串设为全 ‘9’。

质数及前缀和预处理

• 最大可能的数位和为 $9\times18=162$，预先用线性筛算出 isPrime[0..162]，并构造前缀和数组 primeCnt[i] 表示小于等于 i 的质数个数。
• 区间 [lo, hi] 存在质数 当且仅当

  primeCnt[hi] − primeCnt[lo−1] > 0
  

复杂度分析

• 数字长度 $L\le18$。
• 每一位最多枚举 10 个候选数字，并做 $O(1)$ 的区间质数查询。
• 回溯最坏情况也在 $O(L\times10)$ 量级。
• 最多尝试 $L$ 种不同长度，故总体复杂度 $O(L^2\times10)$，常数非常小，可视为 $O(1)$ 级别。

代码实现

Python

import sys

def main():
    s = sys.stdin.readline().strip()
    L = len(s)
    # 预处理质数和前缀和
    MAXS = 9 * 18
    is_prime = [False, False] + [True] * (MAXS - 1)
    for i in range(2, int(MAXS**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, MAXS+1, i):
                is_prime[j] = False
    prime_cnt = [0] * (MAXS + 1)
    cnt = 0
    for i in range(MAXS + 1):
        if is_prime[i]:
            cnt += 1
        prime_cnt[i] = cnt

    # 在上界 bound_str 下搜索最大解，找不到返回空串
    def search(bound_str):
        m = len(bound_str)
        bd = list(map(int, bound_str))
        res = [0] * m

        def dfs(pos, prev, tight, ssum):
            if pos == m:
                return is_prime[ssum]
            max_d = bd[pos] if tight else 9
            for d in range(max_d, prev - 1, -1):
                new_sum = ssum + d
                rem = m - pos - 1
                lo = new_sum + d * rem
                hi = new_sum + 9 * rem
                # 区间 [lo, hi] 必须包含质数
                if lo <= hi and prime_cnt[hi] - (prime_cnt[lo-1] if lo > 0 else 0) == 0:
                    continue
                res[pos] = d
                if dfs(pos+1, d, tight and d == max_d, new_sum):
                    return True
            return False

        return ''.join(map(str, res)) if dfs(0, 1, True, 0) else ''

    # 主流程：先试原长度，再依次尝试全9的更短长度
    ans = ''
    for k in range(L, 0, -1):
        bound = s if k == L else '9' * k
        ans = search(bound)
        if ans:
            print(ans)
            return
    print(-1)

if __name__ == '__main__':
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    static boolean[] isPrime;
    static int[] primeCnt;
    static int[] bd, res;
    static int m;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();
        int L = s.length();
        // 预处理
        int MAXS = 9 * 18;
        isPrime = new boolean[MAXS + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= MAXS; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= MAXS; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        primeCnt = new int[MAXS + 1];
        int cnt = 0;
        for (int i = 0; i <= MAXS; i++) {
            if (isPrime[i]) cnt++;
            primeCnt[i] = cnt;
        }

        // 先试原长度，再试全9的更短长度
        for (int k = L; k >= 1; k--) {
            String bound = (k == L ? s : String.join("", Collections.nCopies(k, "9")));
            String ans = search(bound);
            if (!ans.isEmpty()) {
                System.out.println(ans);
                return;
            }
        }
        System.out.println(-1);
    }

    // 在字符串 bound 下搜索
    static String search(String bound) {
        m = bound.length();
        bd = new int[m];
        res = new int[m];
        for (int i = 0; i < m; i++) bd[i] = bound.charAt(i) - '0';
        return dfs(0, 1, true, 0) ? build() : "";
    }

    // 回溯尝试
    static boolean dfs(int pos, int prev, boolean tight, int sum) {
        if (pos == m) return isPrime[sum];
        int maxD = tight ? bd[pos] : 9;
        for (int d = maxD; d >= prev; d--) {
            int newSum = sum + d;
            int rem = m - pos - 1;
            int lo = newSum + d * rem;
            int hi = newSum + 9 * rem;
            if (lo <= hi && primeCnt[hi] - (lo > 0 ? primeCnt[lo - 1] : 0) == 0)
                continue;
            res[pos] = d;
            if (dfs(pos + 1, d, tight && d == maxD, newSum))
                return true;
        }
        return false;
    }

    static String build() {
        StringBuilder sb = new StringBuilder();
        for (int d : res) sb.append(d);
        return sb.toString();
    }
}

C++

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

const int MAXS = 9 * 18;
bool isPrime[MAXS+1];
int primeCnt[MAXS+1];
string boundStr;
vector<int> bd, res;
int m;

bool dfs(int pos, int prev, bool tight, int sum) {
    if (pos == m) return isPrime[sum];
    int maxD = tight ? bd[pos] : 9;
    for (int d = maxD; d >= prev; d--) {
        int newSum = sum + d;
        int rem = m - pos - 1;
        int lo = newSum + d * rem;
        int hi = newSum + 9 * rem;
        int cnt = primeCnt[min(hi, MAXS)] - (lo > 0 ? primeCnt[lo-1] : 0);
        if (lo <= hi && cnt == 0) continue;
        res[pos] = d;
        if (dfs(pos+1, d, tight && d==maxD, newSum)) return true;
    }
    return false;
}

string searchBound(const string &s) {
    boundStr = s;
    m = s.size();
    bd.assign(m, 0);
    res.assign(m, 0);
    for (int i = 0; i < m; i++) bd[i] = s[i] - '0';
    if (!dfs(0, 1, true, 0)) return "";

    string ans;
    for (int d : res) ans += char('0' + d);
    return ans;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    if (!(cin >> s)) return 0;
    // 预处理质数和前缀和
    fill(isPrime, isPrime+MAXS+1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i*i <= MAXS; i++) {
        if (isPrime[i]) {
            for (int j = i*i; j <= MAXS; j += i)
                isPrime[j] = false;
        }
    }
    int cnt = 0;
    for (int i = 0; i <= MAXS; i++) {
        if (isPrime[i]) cnt++;
        primeCnt[i] = cnt;
    }

    int L = s.size();
    for (int k = L; k >= 1; k--) {
        string bound = (k==L ? s : string(k, '9'));
        string ans = searchBound(bound);
        if (!ans.empty()) {
            cout << ans;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

题目内容

在一个虚拟货币挖矿系统中，每个矿工拥有一定的算力值$n$(范围在$1$ 到$10^{18}$之间)。系统需要为每个矿工分配一个算力档位，这个档位必须是小于等于矿工当前算力$n$的最大“稳定算力档”，并且这个档位的算力值各个数位之和必须是一个质数(质数又称素数。一个大于$1$的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数)。“稳定算力档”定义为从左到右每一位数字都不小于前一位数字，例如$123、111、399$都是符合要求的稳定算力档，像$121、897$

这种则不符合要求。合理分配算力档位有助于提高挖矿效率和稳定性。

输入描述

给定一个正整数$n(1≤n≤10^{18})$

输出描述

返回小于等于$n$的最大稳定算力档，且该整数的所有数位之和为质数。如果不存在这样的整数，则返回$-1$

样例1

输入

111

输出

111

说明

$111$本身即是"稳定算力档"，从左到右每一位数字都不小于前一位数字，$1+1+1=3$是质数，所以函数返回$111$

样例2

输入

1

输出

-1

说明

小于等于$1$的"稳定算力档"只有$1$,$1$的数位之和为$1$,$1$不是质数(质数定义为大于$1$的自然数中，除了$1$和它自身外，不能被其他自然数整除的数)，所以函数返回$-1$

样例3

输入

123

输出

122

说明

首先小于等于$123$的“稳定算力档"有 $123、122、111$等。$123$ 的数位之和为$1+2+3=6$,不是质数，不符合条件。再继续找是$122$，数位之和为$1+2+2=5$是质数符合"稳定算力档条件。$111$的数位之和$1+1+1=3$也为质数也满足"稳定算力档"的条件，但$111$小于$122$，所以小于等于$n$的最大稳定算力档为$122$，函数返回$122$。