[CF776B] Sherlock and His Girlfriend

Description

给定 (n) 个数字，分别为 (2,3,...,n+1)，要对每个数字染色，使得一个数字是另一个数字的质因子时，两个数字的颜色不同，最小化使用的颜色数。求染色方案。

Solution

首先证明一定可以用两种颜色染完。不妨用第一种颜色染所有的质数，用第二种颜色染所有的非质数，显然满足条件。

而当不存在任意两个数使得一个数是另一个数的质因子时，可以用一种颜色染完所有的数。由于数字是 (2,3,4,...,n+1)，这种情况会发生，当且仅当 (n le 2)。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;

int a[N];

signed main()
{
    //ios::sync_with_stdio(false);

    int n;
    cin>>n;
    if(n<=2)
    {
        cout<<1<<endl;
        for(int i=1;i<=n;i++) cout<<1<<" ";
    }
    else
    {
        cout<<2<<endl;
        for(int i=2;i<=n+1;i++)
        {
            if(a[i]==0)
            {
                cout<<1<<" ";
                for(int j=i+i;j<=n+1;j+=i)
                {
                    a[j]=1;
                }
            }
            else
            {
                cout<<2<<" ";
            }
        }
    }
    system("pause");
}