Submission

Score: 60

User: krittaphot

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

Language: cpp

Time: 0.055 second

Submitted On: 2026-03-04 15:16:43

#include <bits/stdc++.h>

using namespace std;
vector<bool> prime(1000001,true);
vector<char> num;
vector<bool> use;
void seive()
{
	prime[0] = false;
	prime[1] = false;
	for(long long i = 2;i*i<=1000000;i++){
		if(prime[i]){
			for(long long j= i*i;j<=1000000;j+=i){
				prime[j] = false;
			}
		}
	}
}

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

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

int main()
{
	long long n,m;
	cin >> n >> m;
	seive();
//	cout << chartonum("5000");
	while(n--){
		string s1;
		cin >> s1;
		num.assign(s1.begin(),s1.begin()+m);
        use.assign(m, 0);
        unordered_map<int,int> seen;
		sort(num.begin(), num.end());
		
		cout << solve(num,m,use,"",seen) << "\n";
	}
}