Note: This article is available in Chinese only. 本文暂无英文版本。
View original
蠢了。
这道题显然可以搜。。
然后自己搜索的姿势果然还是不怎么地。
最后是蔡大神过掉的。
他的思路是枚举素数，然后把素数的各位拆开，看这些数字是否在给出的字符串中出现过。
一开始TLE掉了。
后来又预处理出来一个标记数组，如果字符串中没有数字2，那么20w+的素数就可以直接跳过去，然后A掉了。
其实因为数字的位数最多才7位。
暴力也不是不可以…
STL中求全排列的那个函数我也不是没用过…比赛的时候怎么就没想到==
再开个map判重
然后素数打表部分。
队友是打了个30000+行的表…
说起来…我好像还没用C++写过筛法求素数。。
说来惭愧啊。
pascal的时候倒是写过几次呢。
再复习下…
http://blog.csdn.net/dinosoft/article/details/5829550
写的是快速筛。
代码实现
1/*************************************************************************
2 > File Name: code/2015summer/0821/A.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月20日 星期四 22时17分14秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x7fffffff;
31const int N=1E7+7;
32using namespace std;
33
34bool not_prime[N];
35int prime[N],pri_num;
36map<int,bool> mp;
37int a[N];
38int ans;
39map<int,bool>::iterator it;
40char st[15];
41int len;
42void init()
43{
44
45 not_prime[0] =true;
46 not_prime[1] = true;
47
48 for(int i = 2;i < N; ++i)
49 {
50 if(!not_prime[i])
51 prime[++pri_num] = i;
52 for(int j = 1;j <= pri_num && i * prime[j] < N; j++)
53 {
54
55 not_prime[i * prime[j]] = true;
56 if(i % prime[j] == 0) break;
57 }
58 }
59}
60
61void solve()
62{
63
64 int res = 0;
65 for(int i = 1;i <= len; ++i)
66 {
67
68 res = res * 10 + a[i];
69// cout<<"res:"<<res<<endl;
70 if(!not_prime[res] && !mp[res])
71 {
72 mp[res] = true;
73 ans++;
74 }
75 }
76}
77
78int main()
79{
80 init();
81// for ( int i =2 ; i <= 1000 ; i++)
82// {
83// if (!not_prime[i])
84// {
85// cout<<i<<endl;
86// }
87// }
88 int T;
89 cin>>T;
90 while (T--)
91 {
92
93 ans = 0 ;
94 mp.clear();
95 scanf("%s",st+1);
96 len = strlen(st + 1);
97 for(int i = 1;i <= len; i++)
98 {
99 a[i] = st[i] - '0';
100 }
101 sort(a+1,a+len+1);
102 do
103 {
104 solve();
105 }while (next_permutation(a+1,a+len+1));
106
107
108 printf("%d\n",ans);
109 }
110 return 0;
111}
112
113
114/*************************************************************************
115 > File Name: code/2015summer/0821/A.cpp
116 > Author: 111qqz
117 > Email: rkz2013@126.com
118 > Created Time: 2015年08月20日 星期四 22时17分14秒
119 ************************************************************************/
120
121#include<iostream>
122#include<iomanip>
123#include<cstdio>
124#include<algorithm>
125#include<cmath>
126#include<cstring>
127#include<string>
128#include<map>
129#include<set>
130#include<queue>
131#include<vector>
132#include<stack>
133#define y0 abc111qqz
134#define y1 hust111qqz
135#define yn hez111qqz
136#define j1 cute111qqz
137#define tm crazy111qqz
138#define lr dying111qqz
139using namespace std;
140#define REP(i, n) for (int i=0;i<int(n);++i)
141typedef long long LL;
142typedef unsigned long long ULL;
143const int inf = 0x7fffffff;
144const int N=1E7+7;
145using namespace std;
146
147bool not_prime[N];
148int prime[N],pri_num;
149map<int,bool> mp;
150int a[N];
151int ans;
152map<int,bool>::iterator it;
153char st[15];
154int len;
155void init()
156{
157
158 not_prime[0] =true;
159 not_prime[1] = true;
160
161 for(int i = 2;i < N; ++i)
162 {
163 if(!not_prime[i])
164 prime[++pri_num] = i;
165 for(int j = 1;j <= pri_num && i * prime[j] < N; j++)
166 {
167
168 not_prime[i * prime[j]] = true;
169 if(i % prime[j] == 0) break;
170 }
171 }
172}
173
174void solve()
175{
176
177 int res = 0;
178 for(int i = 1;i <= len; ++i)
179 {
180
181 res = res * 10 + a[i];
182// cout<<"res:"<<res<<endl;
183 if(!not_prime[res] && !mp[res])
184 {
185 mp[res] = true;
186 ans++;
187 }
188 }
189}
190
191int main()
192{
193 init();
194// for ( int i =2 ; i <= 1000 ; i++)
195// {
196// if (!not_prime[i])
197// {
198// cout<<i<<endl;
199// }
200// }
201 int T;
202 cin>>T;
203 while (T--)
204 {
205
206 ans = 0 ;
207 mp.clear();
208 scanf("%s",st+1);
209 len = strlen(st + 1);
210 for(int i = 1;i <= len; i++)
211 {
212 a[i] = st[i] - '0';
213 }
214 sort(a+1,a+len+1);
215 do
216 {
217 solve();
218 }while (next_permutation(a+1,a+len+1));
219
220
221 printf("%d\n",ans);
222 }
223 return 0;
224}