Submission

Score: 0

User: nga12345

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

Language: cpp

Time: 0.015 second

Submitted On: 2025-10-11 10:31:49

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

using namespace std;

int max_n;
vector<bool> is_prime;

void sieve(int limit) {
    is_prime.assign(limit + 1, true);
    is_prime[0] = false;
    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];
}

int countUniquePrimePermutations(const string& digits) {
    int n = digits.size();
    set<int> unique_numbers;
    string sorted_digits = digits;
    sort(sorted_digits.begin(), sorted_digits.end());

    for (int len = 1; len <= n; ++len) {
        vector<bool> mask(n, false);
        fill(mask.end() - len, mask.end(), true);

        do {
            string subset = "";
            for (int i = 0; i < n; ++i) {
                if (mask[i]) subset += sorted_digits[i];
            }
            sort(subset.begin(), subset.end());
            do {
                int number = stoi(subset);
                unique_numbers.insert(number);
            } while (next_permutation(subset.begin(), subset.end()));
        } while (next_permutation(mask.begin(), mask.end()));
    }

    int count = 0;
    for (int num : unique_numbers) {
        if (isPrime(num)) ++count;
    }
    return count;
}

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;
}