地址:http://codeforces.com/contest/1332
题意:细节多多。请一定认真阅读题目!
给出n个合数,对他们进行染色。要求任意两个相同颜色的数gcd>1。颜色的种类不能超过11个。而且如果染了m中颜色,那么1-m都必须每个至少染一次。
解析:唯一分解定理:任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积。两个数,gcd>1,那么这个gcd分到最小质因数,可以说明,这两个数有着共同的最小质因数。对于ai<=1000,31*31==961,所以1000以内的质因数最多到31,恰好是第11个质数。所以我们只要把最小质因数相同的数分成一种颜色就行了。这个颜色要从1开始,而不能对应前11个质因数表的编号,因为要保证1-m中每个至少染一次。
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e3+10; int a[maxn]; int col[15]; int prim[15]={2,3,5,7,11,13,17,19,23,29,31}; int main() { int t; cin>>t; while(t--) { int n; cin>>n; memset(col,0,sizeof(col)); map<int,int>mp; for(int i=1;i<=n;i++) cin>>a[i]; int cnt=0; for(int i=1;i<=n;i++) { for(int j=0;j<11;j++) { if(a[i]%prim[j]==0) { if(col[j]==0) { cnt++; col[j]=cnt; } mp[i]=col[j]; break; } } } cout<<cnt<<endl; for(int i=1;i<n;i++) cout<<mp[i]<<" "; cout<<mp[n]<<endl; } }