Submission

Score: 60

User: Imorange

Problemset: การเรียงสับเปลี่ยน

Language: cpp

Time: 0.014 second

Submitted On: 2026-03-04 19:34:29

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

const int LIM = 1000000;

bool prime[LIM + 1];     
char num[8];            
bool used[8];

int n;
int ans;

void sieve() {
    for(int i = 0; i <= LIM; i++) prime[i] = true;
    prime[0] = prime[1] = false;

    for(int i = 2; i * i <= LIM; i++){
        if(prime[i]){
            for(int j = i * i; j <= LIM; j += i)
                prime[j] = false;
        }
    }
}

void dfs(int depth, int value){
    if(depth == n){
        if(prime[value]) ans++;
        return;
    }

    for(int i = 0; i < n; i++){
        if(used[i]) continue;

        if(i > 0 && num[i] == num[i-1] && !used[i-1]) continue;

        used[i] = true;
        dfs(depth + 1, value * 10 + (num[i] - '0'));
        used[i] = false;
    }
}

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

    int m;
    cin >> m >> n;

    sieve();

    while(m--){
        cin >> num;
        sort(num, num + n);  
        for(int i = 0; i < n; i++)
            used[i] = false;

        ans = 0;
        dfs(0, 0);

        cout << ans << "\n";
    }
}