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

蠢了。

这道题显然可以搜。。

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

最后是蔡大神过掉的。

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

一开始TLE掉了。

后来又预处理出来一个标记数组，如果字符串中没有数字2，那么20w+的素数就可以直接跳过去，然后A掉了。

其实因为数字的位数最多才7位。。

暴力也不是不可以。。。。

STL中求全排列的那个函数我也不是没用过。。。比赛的时候怎么就没想到==

再开个map判重

然后素数打表部分。

队友是打了个30000+行的表。。。。

说起来。。。我好像还没用C++写过筛法求素数。。。

说来惭愧啊。。。。

pascal的时候倒是写过几次呢。

再复习下。。。

http://blog.csdn.net/dinosoft/article/details/5829550

写的是快速筛。

/*************************************************************************
	> File Name: code/2015summer/0821/A.cpp
	> Author: 111qqz
	> Email: rkz2013@126.com 
	> Created Time: 2015年08月20日 星期四 22时17分14秒
 ************************************************************************/

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#define y0 abc111qqz
#define y1 hust111qqz
#define yn hez111qqz
#define j1 cute111qqz
#define tm crazy111qqz
#define lr dying111qqz
using namespace std;
#define REP(i, n) for (int i=0;i<int(n);++i)  
typedef long long LL;
typedef unsigned long long ULL;
const int inf = 0x7fffffff;
const int N=1E7+7;
using namespace std;

bool not_prime[N];
int prime[N],pri_num;
map<int,bool> mp;
int a[N];
int ans;
map<int,bool>::iterator it;
char st[15];
int len;
void init()
{

    not_prime[0] =true;
    not_prime[1] = true;

    for(int i = 2;i < N; ++i) 
    {
	if(!not_prime[i])
	    prime[++pri_num] = i;
	for(int j = 1;j <= pri_num && i * prime[j] < N; j++) 
	{

	    not_prime[i * prime[j]] = true;
	    if(i % prime[j] == 0)   break;  
	}
    }
}
    
void solve()
{
    
    int res = 0;
    for(int i = 1;i <= len; ++i) 
    {

	res = res * 10 + a[i];
//	cout<<"res:"<<res<<endl;
	if(!not_prime[res] && !mp[res])
	{
	    mp[res] = true;
	    ans++;
	}
    }
}

int main()
{
	init();
//	for ( int i =2 ; i <= 1000 ; i++)
//	{
//	    if (!not_prime[i])
//	    {
//		cout<<i<<endl;
//	    }
//	}
	int T;
	cin>>T;
	while (T--)
	{
		
		ans = 0 ;
		mp.clear();
		scanf("%s",st+1);
		len = strlen(st + 1);
		for(int i = 1;i <= len; i++)
		{
			a[i] = st[i] - '0';
		}
		sort(a+1,a+len+1);
		  do
		    {
			solve();
		    }while (next_permutation(a+1,a+len+1));
		

		printf("%d\n",ans);
	}
	return 0;
}


/*************************************************************************
	> File Name: code/2015summer/0821/A.cpp
	> Author: 111qqz
	> Email: rkz2013@126.com 
	> Created Time: 2015年08月20日 星期四 22时17分14秒
 ************************************************************************/

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#define y0 abc111qqz
#define y1 hust111qqz
#define yn hez111qqz
#define j1 cute111qqz
#define tm crazy111qqz
#define lr dying111qqz
using namespace std;
#define REP(i, n) for (int i=0;i<int(n);++i)  
typedef long long LL;
typedef unsigned long long ULL;
const int inf = 0x7fffffff;
const int N=1E7+7;
using namespace std;

bool not_prime[N];
int prime[N],pri_num;
map<int,bool> mp;
int a[N];
int ans;
map<int,bool>::iterator it;
char st[15];
int len;
void init()
{

    not_prime[0] =true;
    not_prime[1] = true;

    for(int i = 2;i < N; ++i) 
    {
	if(!not_prime[i])
	    prime[++pri_num] = i;
	for(int j = 1;j <= pri_num && i * prime[j] < N; j++) 
	{

	    not_prime[i * prime[j]] = true;
	    if(i % prime[j] == 0)   break;  
	}
    }
}
    
void solve()
{
    
    int res = 0;
    for(int i = 1;i <= len; ++i) 
    {

	res = res * 10 + a[i];
//	cout<<"res:"<<res<<endl;
	if(!not_prime[res] && !mp[res])
	{
	    mp[res] = true;
	    ans++;
	}
    }
}

int main()
{
	init();
//	for ( int i =2 ; i <= 1000 ; i++)
//	{
//	    if (!not_prime[i])
//	    {
//		cout<<i<<endl;
//	    }
//	}
	int T;
	cin>>T;
	while (T--)
	{
		
		ans = 0 ;
		mp.clear();
		scanf("%s",st+1);
		len = strlen(st + 1);
		for(int i = 1;i <= len; i++)
		{
			a[i] = st[i] - '0';
		}
		sort(a+1,a+len+1);
		  do
		    {
			solve();
		    }while (next_permutation(a+1,a+len+1));
		

		printf("%d\n",ans);
	}
	return 0;
}


v