HUST team contest #2 A An Industrial Spy ||poj 3842 (筛)

An Industrial Spy

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1483		Accepted: 602

Description

Industrial spying is very common for modern research labs. I am such an industrial spy - don't tell anybody! My recent job was to steal the latest inventions from a famous math research lab. It was hard to obtain some of their results but I got their waste out of a document shredder.
I have already reconstructed that their research topic is fast factorization. But the remaining paper snippets only have single digits on it and I cannot imagine what they are for. Could it be that those digits form prime numbers? Please help me to find out how many prime numbers can be formed using the given digits.

Input

The first line of the input holds the number of test cases c (1 <= c <= 200). Each test case consists of a single line. This line contains the digits (at least one, at most seven) that are on the paper snippets.

Output

For each test case, print one line containing the number of different primes that can be reconstructed by shuffling the digits. You may ignore digits while reconstructing the primes (e.g., if you get the digits 7 and 1, you can reconstruct three primes 7, 17, and 71). Reconstructed numbers that (regarded as strings) differ just by leading zeros, are considered identical (see the fourth case of the sample input).

Sample Input

Sample Output

Source

2009 ACM North Western European Regional Contest

蠢了。

这道题显然可以搜。。

然后自己搜索的姿势果然还是不怎么地。。

最后是蔡大神过掉的。

他的思路是枚举素数，然后把素数的各位拆开，看这些数字是否在给出的字符串中出现过。

一开始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
 26 using namespace std;
 27 #define REP(i, n) for (int i=0;i<int(n);++i)  
 28 typedef long long LL;
 29 typedef unsigned long long ULL;
 30 const int inf = 0x7fffffff;
 31 const int N=1E7+7;
 32 using namespace std;
 33 
 34 bool not_prime[N];
 35 int prime[N],pri_num;
 36 map<int,bool> mp;
 37 int a[N];
 38 int ans;
 39 map<int,bool>::iterator it;
 40 char st[15];
 41 int len;
 42 void 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     
 61 void 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 
 78 int 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
",ans);
109     }
110     return 0;
111 }

View Code