Submission

Score: 60

User: krittaphot

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

Language: cpp

Time: 0.096 second

Submitted On: 2026-03-04 14:57:09

#include <bits/stdc++.h>

using namespace std;
vector<bool> prime(1000001,true);

void seive()
{
	prime[0] = false;
	prime[1] = false;
	for(int i = 2;i*i<=1000000;i++){
		if(prime[i]){
			for(int j= i*i;j<=1000000;j+=i){
				prime[j] = false;
			}
		}
	}
}

int chartonum(string s){
    int sum = 0;
    for(char c : s){
        sum = sum*10 + (c - '0');
    }
    return sum;
}

int solve(vector<char> &num,int n,vector<bool> use,string s1,vector<bool> &seen){
	if(s1.size() == n){
		if(prime[chartonum(s1)] && !seen[chartonum(s1)]){
			seen[chartonum(s1)] = true;
			return 1;
		}
		else{
			return 0;
		}
	}
	int sum = 0;
	for(int i = 0;i<n;i++){
		if(use[i] == false){
			use[i] = true;
			sum += solve(num,n,use,s1+num[i],seen);
			use[i] = false;
		}
	}
	return sum;
}

int main()
{
	int n,m;
	cin >> n >> m;
	seive();
//	cout << chartonum("5000");
	while(n--){
		string s1;
		cin >> s1;
		vector<bool> seen(1000001,false);
		vector<char> num(m);
		vector<bool> use(m,false);
		for(int i = 0;i<m;i++){
			num[i] = s1[i];
		}
		
		cout << solve(num,m,use,"",seen) << "\n";
	}
}