Submission

Score: 60

User: muekwakungaroo

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

Language: cpp

Time: 0.085 second

Submitted On: 2026-03-05 09:49:53

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>m>>n;
    int ar[n];
    char ch;
    vector<bool> isprime(pow(10,n),true);
    isprime[1]=false;
    isprime[0]=false;
    for(int i=2;i<=pow(10,n)/i;i++){
        for(int j=i*i;j<pow(10,n);j+=i){
            if(isprime[j]==true){
                isprime[j]=false;
            }
        }
    }
    int sum,cnt;
    int s=pow(10,n);
    int dp[s];
    memset(dp,-1,sizeof(dp));
    while(m--){
        for(int i=0;i<n;i++){
            cin>>ch;
            ar[i]=ch-'0';
        }
        sort(ar,ar+n,greater<int>());
        sum=0;
        for(int i=0;i<n;i++){
            sum+=(ar[i]*pow(10,n-i-1));
        }
        if(dp[sum]!=-1){
            cout<<dp[sum]<<'\n';
            continue;
        }
        sort(ar,ar+n);
        sum=0;
        cnt=0;
        do{
            sum=0;
            for(int i=0;i<n;i++){
                sum+=(ar[i]*pow(10,n-i-1));
            }
            if(isprime[sum]){
                cnt++;
                // cout<<sum<<' ';
            }
        }while(next_permutation(ar,ar+n));
        dp[sum]=cnt;
        cout<<cnt<<'\n';
    }
    return 0;
}