AcWing 1293. 夏洛克和他的女朋友(思维欧拉筛图论）

glm233

发布于 2021-03-02 15:09:03

4410

文章被收录于专栏：glm的全栈学习之路glm的全栈学习之路

夏洛克有了一个新女友（这太不像他了！）。

情人节到了，他想送给女友一些珠宝当做礼物。

他买了 nn 件珠宝，第 ii 件的价值是 i+1i+1，也就是说，珠宝的价值分别为 2,3,…,n+12,3,…,n+1。

华生挑战夏洛克，让他给这些珠宝染色，使得一件珠宝的价格是另一件珠宝的价格的质因子时，两件珠宝的颜色不同。

并且，华生要求他使用的颜色数尽可能少。

请帮助夏洛克完成这个简单的任务。

输入格式

只有一行一个整数 nn，表示珠宝件数。

输出格式

第一行一个整数 kk，表示所使用的颜色数；

第二行 nn 个整数，表示第 11 到第 nn 件珠宝被染成的颜色。

若有多种答案，输出任意一种。

请用 11 到 kk 表示你用到的颜色。

数据范围

1≤n≤1051≤n≤105

输入样例1：

输出样例1：

2
1 1 2

输入样例2：

输出样例2：

2
2 1 1 2

思路：我们可以将所有2-n+1的数抽象为一张图上的点，如果一个数比如6有质因子2，那么就是2->6连一条边，可以发现这张图的所有边都是质数连向合数因为不可能是合数连向合数

那么其实本质这道题就是二分图匹配小于三只有质数 1一种颜色其他都是两种颜色染色方式就是质数全部染相同合数另外一种颜色

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,pr[N],cnt;
bool st[N];
void init(int n){
    for(int i=2;i<=n;i++){
        if(!st[i])pr[cnt++]=i;
        for(int j=0;pr[j]*i<=n;j++){
            st[i*pr[j]]=1;
            if(i%pr[j]==0)break;
        }
    }
}
int main(){
    cin>>n;
    init(n+1);
    if(n<=2){
        puts("1");
        for(int i=1;i<=n;i++)printf("1 ");
    }
    else{
        puts("2");
        for(int i=1;i<=n;i++){
            if(st[i+1])printf("2 ");
            else printf("1 ");
        }
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/02/23 ，如有侵权请联系 cloudcommunity@tencent.com 删除