Submission

Score: 60

User: nga12345

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

Language: cpp

Time: 0.007 second

Submitted On: 2025-10-11 09:53:25

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

using namespace std;

int max_n;
vector<bool> is_prime;
vector<int> primes;

bool isPrime(int x) {
    return x >= 2 && x <= max_n && is_prime[x];
}

int countUniquePrimePermutations(const string& digits) {
    set<int> unique_numbers;
    string s = digits;
    sort(s.begin(), s.end());
    do {
        int number = stoi(s);
        unique_numbers.insert(number);
    } while (next_permutation(s.begin(), s.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 num_cases, length;
    cin >> num_cases;
    cin >> length;

    max_n = pow(10, length) - 1;
    is_prime.resize(max_n + 1, true);

    is_prime[0] = is_prime[1] = false;
    int limit = sqrt(max_n);
    for (int i = 2; i <= limit; ++i) {
        if (!is_prime[i]) continue;
        for (int j = i * i; j <= max_n; j += i) {
            is_prime[j] = false;
        }
    }
    for (int i = 2; i <= max_n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        };
    }

    while (num_cases--) {
        string input;
        cin >> input;
        cout << countUniquePrimePermutations(input) << '\n';
    }

    return 0;
}