# 题意

题目链接

输入 tt 表示 nn 的数量,输入 tt 个整数 nn
对于每个 nn,将 nn 的每一位拆出来组成一个序列。记该序列为 NN
NN 进行全排列,输出 NN 的某个排列按照顺序组成的数是素数的排列的数量。

# 举例

比如 n=123n=123,则 N={1,2,3}N=\{1,2,3\}
那么 NN 的全排列是:

{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}\{1,2,3\},\{1,3,2\},\{2,1,3\},\{2,3,1\},\{3,1,2\},\{3,2,1\}

上面的每个序列按照顺序组成的数是:

123,132,213,231,312,321123,132,213,231,312,321

上面的数中没有数是素数,那么就输出 00

# 分析

本题有两个重要步骤:

  1. 生成全排列
  2. 判断是否是素数

# 步骤 1

用 DFS 的方式枚举每一种排列。

设当前在求解 [l,r][l,r] 区间的元素的全排列。
如果 l=rl=r,则意味着当前已经生成了一次排列,可以开始判断是否是素数了,
否则遍历当前区间的每一个元素,
将当前遍历到的元素放到当前区间的首位,即第 ll 位,
递归求解 [l+1,r][l+1,r]
求解后回溯,将当前区间的第 11 个元素,即第 ll 个元素放回原位。
然后…… 妥妥的
TLE

用递归的方式求解全排列时间复杂度过高,于是我们可以用 STL 库中的 next_permutation 来生成全排列。

具体细节请看代码。

# 步骤 2

可以用线性筛的方法先筛出来有哪些数是质数。

考虑对于任意一个大于 11 的正整数 nn,那么它的 xx 倍就是合数(x>1x > 1)。
如果我们从小到大遍历每个数,把当前的数的所有比自己大的倍数标记为合数,那么遍历完成后没有被标记的数就是素数了。
这就是埃氏筛法,时间复杂度 O(nloglogn)O(n\log\log n)

埃氏筛法会将一个合数多次标记,如果能让每个合数都只被标记一次,那么时间复杂度就可以降到 O(n)O(n) 了,这就是线性筛。
具体步骤请看代码。

(以上内容改编自 OI-Wiki

# 代码

#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
// 调试时用来输出日志的,请忽略
//#define DEBUG
using std::next_permutation, std::sort, std::swap;
using std::cin, std::cout, std::endl;
using std::string;
const int N = 10000000;
int t, n;
// 用来存放 n 的每一位
int nArray[11];
// 用来存放 n 的数位个数
int nArrayLength;
// 是否是素数的 bool 数组
bool isPrime[N + 1];
// 素数的个数
int primeCount;
// 记录素数
int prime[N + 1];
//// 用于全排列时去除重复元素
// bool isAPermNArray[N + 1];
// 记录答案
int answer;
// 调试时用来输出日志的,请忽略
void log ( string logString ) {
    #ifdef DEBUG
    cout << logString;
    #endif
}
// 调试时用来输出日志的,请忽略
void logln ( string logString ) {
    #ifdef DEBUG
    cout << logString << '\n';
    #endif
}
// 用线性筛法筛出素数,以初始化 isPrime 数组
void initIsPrime ( ) {
    memset ( isPrime, true, sizeof isPrime );
    // 0 和 1 不是素数
    isPrime[ 0 ] = false;
    isPrime[ 1 ] = false;
    for ( int i = 2; i <= N; ++ i ) {
        // 如果当前遍历到的数是素数
        if ( isPrime[ i ] ) {
            // 记录
            ++ primeCount;
            prime[ primeCount ] = i;
        }
        // 此处详见:
        // https://www.jianshu.com/p/f16d318efe9b
        for ( int j = 1; j <= primeCount && i * prime[ j ] <= N; ++ j ) {
            isPrime[ i * prime[ j ] ] = false;
            if ( i % prime[ j ] == 0 ) {
                break;
            }
        }
    }
}
// 用递归枚举全排列会超时
//
//// 遍历当前求解的全排列区间的每个元素,
//// 将遍历到的元素提到当前区间的首位,
//// 剩下的元素组成的区间递归求解全排列
// void permNArray ( int l, int r ) {
//     // 当前区间只有一个元素,
//     // 意味着到达递归边界
//     if ( l == r ) {
//         // 将当前的 nArray 存放到 int 变量中,用以判断当前排列是否为素数
//         int nNow = 0;
//         // 有前导 0
//         if ( nArray[ 1 ] == 0 ) {
//             return;
//         }
//         for ( int i = 1; i <= nArrayLength; ++ i ) {
//             nNow = nNow * 10 + nArray[ i ];
//         }
//         // 不是之前出现过的排列,并且是素数
//         if ( ( ! isAPermNArray[ nNow ] ) && isPrime[ nNow ] ) {
//             // 记录答案
//             ++ answer;
//         }
//         isAPermNArray[ nNow ] = true;
//     }
//     else {
//         for ( int i = l; i <= r; ++ i ) {
//             // 将第 i 个元素提到首位
//             swap ( nArray[ l ], nArray[ i ] );
//             // 对剩下的元素组成的区间递归求解其全排列
//             permNArray ( l + 1, r );
//             // 回溯,将刚才提到首位的元素放回原处
//             swap ( nArray[ l ], nArray[ i ] );
//         }
//     }
// }
int main ( ) {
    std::ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    cout.tie ( 0 );
    initIsPrime ( );
    cin >> t;
    for ( int tLoop = 1; tLoop <= t; ++ tLoop ) {
        cin >> n;
        // 不要忘记初始化
        memset ( nArray, 0, sizeof nArray );
        nArrayLength = 0;
        // for ( int i = 1; i <= n; ++ i ) {
        //     isAPermNArray[ i ] = false;
        // }
        answer = 0;
        // 提取出 n 的每一位放到 nArray 数组
        for ( int i = 1; i <= 10; ++ i ) {
            if ( n <= 0 ) {
                break;
            }
            else {
                nArray[ i ] = n % 10;
                ++ nArrayLength;
                n /= 10;
            }
        }
        // 一定要排序,不然无法枚举到所有的排列
        sort ( nArray + 1, nArray + nArrayLength + 1 );
        do {
            // 将当前的 nArray 存放到 int 变量中,用以判断当前排列是否为素数
            int nNow = 0;
            // 有前导 0
            if ( nArray[ 1 ] == 0 ) {
                continue;
            }
            for ( int i = 1; i <= nArrayLength; ++ i ) {
                nNow = nNow * 10 + nArray[ i ];
            }
            if ( isPrime[ nNow ] ) {
                ++ answer;
            }
        }
        //next_permutation 会生成序列的所有不同排列,并在枚举完所有排列后返回 false
        while ( next_permutation ( nArray + 1, nArray + nArrayLength + 1 ) );
        cout << answer << '\n';
    }
    cout << endl;
    return 0;
}

AC 记录

此文章已被阅读次数:正在加载...更新于

感谢赞赏

枫上天游 微信支付

微信支付

枫上天游 支付宝

支付宝