Luogu CF1174C 题解

这道题其实不难。

\(\gcd(i,j)=1\)，其实就是 \(i\) 与 \(j\) 互质。

如果 \(i\) 与 \(j\) 不互质，那么我们一定要让 \(a_i\) 与 \(a_j\) 相同，只有这样，才能使 \(a\) 序列中的最大值最小化。

所以，我们可以使用埃氏筛法，当筛到质数时，给它和它的倍数都赋值为一个新数。

AC Code:

#include<iostream>
using namespace std;
int n;
int a[100005];
int c;
signed main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        if(a[i])continue; //非质数
        c++; //一个新数字
        for(int j=1;j*i<=n;j++){
            a[i*j]=c; //倍数赋值为 c
        }
    }
    for(int i=2;i<=n;i++){ //从 2 开始
        cout<<a[i]<<" ";
    }
    return 0; //完美收尾
}