题目大意:n组数据,每组数据给出不超过7个数字,将这些数字排列,问能组成多少个素数。
思路:观察数据范围,7个数字,最多就是10^7个数,开一个bool就能存下那些是素数。当然最好还是线性筛,O(n)处理出来。然后组合数字当然可以搜索,但是我比较偷懒,直接全排列了。然后再为了防止重复计数,用一个map存一下是否搜过。就这样乱搞过了。
CODE:
#include <map> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define INF 10000000 #define MAX 1000010 using namespace std; map<int,bool> G; int cases; int temp,src[MAX],cnt,ans; bool not_prime[INF]; int prime[MAX],primes; char s[10]; void Pretreatment(); inline void Initialize(); inline void Judge(); int main() { Pretreatment(); for(cin >> cases;cases; --cases) { Initialize(); scanf("%s",s + 1); cnt = strlen(s + 1); for(int i = 1;i <= cnt; ++i) src[i] = s[i] - '0'; sort(src + 1,src + cnt + 1); do Judge(); while(next_permutation(src + 1,src + cnt + 1)); printf("%d\n",ans); } return 0; } void Pretreatment() { not_prime[0] = not_prime[1] = true; for(int i = 2;i < INF; ++i) { if(!not_prime[i]) prime[++primes] = i; for(int j = 1;j <= primes && i * prime[j] < INF; ++j) { not_prime[i * prime[j]] = true; if(i % prime[j] == 0) break; } } } inline void Initialize() { cnt = ans = 0; G.clear(); } inline void Judge() { int now = 0; for(int i = 1;i <= cnt; ++i) { now = now * 10 + src[i]; if(!not_prime[now] && !G[now]) G[now] = true,ans++; } }