【NOI六连测】[D6T1] 互质

题目传送门：http://pan.baidu.com/s/1eR1sqXk
离线版题目：http://paste.ubuntu.com/18699825/
数据传送门：http://pan.baidu.com/s/1o8pgYZg

这个题目，暴力的状压很容易想到，然而质因数太多，数组开不下 QAQ
于是考试的时候，码个暴力就闪人了。一看题解，真的是好妙啊！o(￣▽￣)ブ

我们只拆分33以内的质因数，这里只有12个，可以承受。
这么干，还有一个好处：对于一个1k以内的数，超过33的质因数只可能有一个
也就是说，我们对于任意一个数，分两种情况讨论：
1）只有33以内的质因数：这样的话，直接暴力转移即可
2）有33以上的质因数：将拥有相同的、大于33的质因数的数存成一组，像分组背包一样一起转移
因为大于33的质因数只可能有一个，而相同的存在了一起，所以只要保证小于34的质因数不重合即可

此题真的是妙啊！

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 5000;
const int LIM = 4500;
const int N = 12;

int sed[]={0,2,3,5,7,11,13,17,19,23,29,31,33};
int n,que[MAXN][MAXN],cnt[MAXN];
int t1[MAXN],t2[MAXN],*f,*g;

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

int main(){
	freopen("prime.in","r",stdin);
	freopen("prime.out","w",stdout);
	n = read();
	f=t1; g=t2;
	
	for (int i=1,a;i<=n;i++){
		a = read();
		int tmp = a, buf = 0;
		for (int i=1;i<=N;i++) if (!(tmp%sed[i])) {
			while (!(tmp%sed[i])) tmp /= sed[i];
			buf |= 1<<(i-1);
		} 
		if (tmp != 1) que[tmp][++cnt[tmp]] = buf;
		else for (int i=1;i<=LIM;i++) if (!(i&buf)) 
			f[i|buf] = max(f[i|buf], f[i]+1);
	}
	
	for (int i=1;i<=1000;i++){
		for (int k=1;k<=LIM;k++) g[k] = f[k];
		for (int j=1;j<=cnt[i];j++)	for (int k=1;k<=LIM;k++)
			if (!(k&que[i][j])) g[k|que[i][j]] = max(g[k|que[i][j]], f[k]+1);		
		swap(g,f);
	}
	
	int vout = 1;
	for (int i=1;i<=LIM;i++)
		vout = max(vout, f[i]);
	printf("%d\n",vout);
	
	return 0;
}	

—————————— UPD 2017.2.1 ——————————
总感觉这个题DLX可以暴力过的样子
有没有同学有空写写啊！