Sherlock and His Girlfriend

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1019 字

n件珠宝价值为2..n+1；若一件价格是另一

一本通
练习

正文

/*
原题：T1623「一本通 6.2 练习 4」Sherlock and His Girlfriend（CF 400B）
题意：n 件珠宝价值为 2..n+1；若一件价格是另一件价格的质因子，则二者颜色须不同，求最少颜色数并给出一种染色。
思路：约束只在“质数 p — p 的倍数（合数）”之间，质数之间、合数之间无边，故二分图，最少 2 色（n≤2 时为 1 色）。
染色：价值为质数染 1，为合数染 2，即为合法方案（任意合法方案均判对）。
复杂度：时间 O(n log log n)，空间 O(n)
易错点：1) 最少颜色数 k：n≤2 输出 1，否则 2；2) 价值是 i+1 而非 i；3) 任意合法染色均被接受。
*/
#include <bits/stdc++.h>
using namespace std;
const int MAX=1000005;
vector<bool> isp(MAX,true);
void sieve(){
    isp[0]=isp[1]=false;
    for(int i=2;i*i<MAX;i++){
        if(isp[i]){
            for(int j=i*i;j<MAX;j+=i){
                isp[j]=false;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    sieve();
    int n;
    cin>>n;
    if(n<=2){
        cout<<1<<"\n";
        for(int i=1;i<=n;i++){
            cout<<(i==1?"1":" 1");
        }
        cout<<"\n";
        return 0;
    }
    cout<<2<<"\n";
    for(int i=1;i<=n;i++){
        int v=i+1;
        int c=isp[v]?1:2;
        cout<<(i==1?"":" ")<<c;
    }
    cout<<"\n";
    return 0;
}

Sherlock and His Girlfriend

正文

一本通·提高篇的其它内容