Submission

Score: 60

User: iij

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

Language: cpp

Time: 0.004 second

Submitted On: 2025-10-22 20:28:58

#include <iostream>
#include <algorithm>

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

string nextPer(string n) {
    string s = n;
    int pivot = -1;
    for (int i = s.length()-2; i >= 0; i--) {
        if (s[i] < s[i+1]) {
            pivot = i;
            break;
        }
    }
    if (pivot == -1) {
        reverse(s.begin(), s.end());
        return s;
    }
    for (int i = s.length()-1; i > pivot; i--) {
        if (s[i] > s[pivot]) {
            swap(s[i], s[pivot]);
            break;
        }
    }
    reverse(s.begin()+pivot+1, s.end());
    return s;
}

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, last;
        cin >> last;
        s = last;

        do {
            if (!isNotPrime[stoi(s)]) ans[i]++;
            s = nextPer(s);
        } while (s != last);
    }

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