优质牛肋骨

Original Link

思想：

• DFS。
  • 从小到大依次枚举所有的数显然不现实，因此考虑按位枚举。
  • 枚举从最高位开始，之后枚举每一位的数，直到达到指定位数为止。
  • 枚举每一位后，需要判断当前位的数和高位数的组合数是否为质数，只有如此才能满足条件。
  • 举例说明对于 \(7331\) 的枚举过程：
    • 第一位为 \(7\)，是质数，枚举下一位；
    • 第二位为 \(3\)，与高位数组合为 \(73\) 是质数，枚举下一位；
    • 第三位为 \(3\)，与高位数组合为 \(733\) 是质数，枚举下一位；
    • 第四位为 \(1\)，与高位数组合为 \(7331\) 是质数，达到了位数条件即为所求。
  • 由上述例子可知，最高位必定取值为 \(\{2, 3, 5, 7\}\)，且后续添加的数不能为偶数（从 \(1\) 枚举到 \(9\) 后续再判断也可以）。
  • 因此，递归的每一层，枚举剩余位从 \(0\) 开始枚举到 \(9\) 与高位数组合判断。
  • 若组合数为质数，则递归到下一层，否则跳过。
  • 最终满足的组合数直接输出即可。

代码1（数组存方案版）：

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

int n;

int pos[] = {2, 3, 5, 7};  //最高位必为其中之一
int add[] = {1, 3, 5, 7, 9};

int ans[10];  // 存储组合数的每一位

bool is_prime(int x){  // 判断是否为质数
    if(x < 2) return 0;
    for(int i = 2; i <= x / i; i ++){
        if(x % i == 0) return 0;
    }
    return 1;
}

int sum(int u, int x){  // 构造高位数并加上当前位，形成完整数字
    int t = 0;
    for(int i = 0; i < u; i ++){  // 循环构造高位数
        t = t * 10 + ans[i];
    }
    return t * 10 + x;
}

void dfs(int u){
    if(u == n){  // 满足位数输出
        for(int i = 0; i < u; i ++) cout << ans[i];
        cout << endl;
        return ;
    }
    for(int i = 0; i < 5; i ++){
        if(is_prime(sum(u, add[i]))){  // 满足与高位数组合为质数
            ans[u] = add[i];  // 将当前位记录
            dfs(u + 1);  // 枚举下一位
        }
    }
}

void solve(){
    cin >> n;
    for(int i = 0; i < 4; i ++){
        ans[0] = pos[i];  // 最高位
        dfs(1);  // 从最高位的下一位开始枚举
    }
}

int main(){
    solve();
    return 0;
}

代码2（优化空间版）：

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

int n;

int pos[] = {2, 3, 5, 7};
int add[] = {1, 3, 5, 7, 9};

bool is_prime(int x){
    if(x < 2) return 0;
    for(int i = 2; i <= x / i; i ++){
        if(x % i == 0) return 0;
    }
    return 1;
}

void dfs(int u, int ans){  // 将答案直接用 ans 表示
    if(u == n){
        cout << ans << endl;
        return ;
    }
    for(int i = 0; i < 5; i ++){
        int t = ans * 10 + add[i];  // 和高位数组合的数
        if(is_prime(t)) dfs(u + 1, t);  // 满足为质数递归枚举下一位
    }
}

void solve(){
    cin >> n;
    for(int i = 0; i < 4; i ++) dfs(1, pos[i]);  // 最高位从 pos[i] 开始，即 ans = pos[i]
}

int main(){
    solve();
    return 0;
}