CodeForces - 1332B Composite Coloring(数论+构造)

题目链接：点击查看

题目大意：给出 n 个合数，每个数不超过 1000 ，现在要求给每个数涂上颜色，使得相同颜色的任意两个数的 gcd 都大于 1 ，现在问在总颜色数不超过 11 种的情况下，构造出一种可行方案

题目分析：因为每个数不超过 1000 所以可以考虑质因子分解，又因为每个数都是合数，所以每个数都可以被拆分出至少两个质因子，而第 12 个质数为 37 ，37 * 37 > 1000 ，所以根据质因子分配颜色是可行的，于是直接实现就好了，比赛时用了vector，赛后发现用map会更简单一些

代码：
 

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;map<int,int>mp;int ans[N];int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){mp.clear();int n,cnt=0;scanf("%d",&n);for(int i=1;i<=n;i++){int num;scanf("%d",&num);for(int j=2;j<=num;j++)if(num%j==0){if(mp[j])ans[i]=mp[j];elsemp[j]=ans[i]=++cnt;break;}}printf("%d\n",cnt);for(int i=1;i<=n;i++)printf("%d ",ans[i]);puts("");}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1332B Composite Coloring(数论+构造)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。