Submission

Score: 60

User: nga12345

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

Language: cpp

Time: 0.005 second

Submitted On: 2025-10-11 10:34:24

#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) {
    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 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;
}