CF1174C 题解
I_like_magic
·
·
题解
这道题其实不难。
如果 $i$ 与 $j$ 不互质，那么我们一定要让 $a_i$ 与 $a_j$ 相同，只有这样，才能使 $a$ 序列中的最大值最小化。
所以，我们可以使用埃氏筛法，当筛到质数时，给它和它的倍数都赋值为一个新数。
AC Code:
```cpp
#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; //完美收尾
}
```