Submission

Score: 60

User: iij

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

Language: cpp

Time: 0.005 second

Submitted On: 2025-10-22 20:53:43

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;
int ans[1025], mx[7] = {0, 0, 100, 1000, 10000, 100000, 1000000};
bool isNotPrime[1000000];

void permRec(string &s, int idx, int &sum, set<int> &dupe) {
    if (idx == s.length()) {
        int p = stoi(s);
        if (!isNotPrime[p] && dupe.find(p) == dupe.end()) {
            sum++;
            dupe.insert(p);
        }
        return;
    }

    for (int i = idx; i < s.length(); i++) {
        swap(s[idx], s[i]);
        permRec(s, idx+1, sum, dupe);
        swap(s[idx], s[i]);
    }
}

int main() {
    isNotPrime[0] = isNotPrime[1] = 1;
    
    int n, m;
    cin >> n >> m;

    for (int i = 2; i*i <= mx[m]; i++) {
        if (!isNotPrime[i])
        for (int j = i*i; j <= mx[m]; j+=i) {
            isNotPrime[j] = 1;
        }
    }

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int c = 0;
        set<int> d;
        permRec(s, 0, c, d);
        ans[i] = c;
    }

    for (int i = 0; i < n; i++) cout << ans[i] << "\n";
}