Submission

Score: 0

User: nga12345

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

Language: cpp

Time: 0.009 second

Submitted On: 2025-10-11 11:07:35

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int max_n;
vector<bool> is_prime;

void sieve(int limit) {
    is_prime.assign(limit + 1, true);
    if (limit >= 0) is_prime[0] = false;
    if (limit >= 1) is_prime[1] = false;
    int sqrt_limit = sqrt(limit);
    for (int i = 2; i <= sqrt_limit; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= limit; j += i)
                is_prime[j] = false;
        }
    }
}

bool isPrime(int num) {
    if (num < 0 || num >= (int)is_prime.size()) return false;
    return is_prime[num];
}

set<int> unique_primes_found;

void generate_numbers(
    const string& all_digits, 
    string& current_number_str, 
    vector<bool>& used) 
{
    if (!current_number_str.empty()) {
        int number = stoi(current_number_str);
        
        if (number < (int)is_prime.size()) { 
            if (isPrime(number)) {
                unique_primes_found.insert(number);
            }
        }
    }
    
    for (int i = 0; i < (int)all_digits.length(); ++i) {
        if (!used[i]) {
            if (i > 0 && all_digits[i] == all_digits[i-1] && !used[i-1]) {
                continue;
            }

            used[i] = true;
            current_number_str.push_back(all_digits[i]);

            generate_numbers(all_digits, current_number_str, used);

            current_number_str.pop_back();
            used[i] = false;
        }
    }
}

int countUniquePrimePermutations(const string& digits) {
    unique_primes_found.clear();

    string sorted_digits = digits;
    sort(sorted_digits.begin(), sorted_digits.end()); 
    
    string current_number_str;
    vector<bool> used(sorted_digits.length(), false);

    generate_numbers(sorted_digits, current_number_str, used);

    return unique_primes_found.size();
}

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

    int m, length;
    cin >> m >> length; 

    max_n = pow(10, length) - 1;
    sieve(max_n);

    for (int i = 0; i < m; ++i) {
        string input;
        cin >> input;
        cout << countUniquePrimePermutations(input) << '\n';
    }

    return 0;
}