8.6 label

题目大意

给定整数 \(n\) ，要求构造一个序列 \(a\) ，满足如下条件。

• 对于两个整数 \(i\) , \(j\) ，若 \(1 \le i<j \le n\) ，且 \(i\) 是 \(j\) 的约数，那么 \(a_i \neq a_j\) 。

请输出 \(\max\{a_1,a_2,\dots,a_n\}\) 最小的序列。

数据范围

\(1 \le n \le 10^5\) 。

思路概述

因为一个数的颜色不能与其因子相同，所以考虑这样一种染色法：对于 \(1\) ，我们特殊地将其染色为 \(1\) ；而对于其他数，我们给它染上除了它自身的最大因子（这里不规范地暂且将其称为“次大因子”）的颜色加一。

下面证明正确性。也就是要证明这个做法的答案最小性和满足条件性。

先证满足条件性。即证下面这个命题：对于一个数，它的次大因子的颜色不比更小的因子的颜色更小。将这个数进行质因数分解，那么每个它的因子肯定都是由这些质因数组成的，所以更大的因子肯定是更小的因子的倍数，那么就说明：更小的因子肯定是更大的因子的因子，那么最大的“更小因子”的颜色肯定是要小于次大因子的颜色的。那么这样递推下去，就能得到：次大因子的颜色不比更小的因子的颜色更小。

然后来证明答案最小性。这个性质也可以换一种说法，即答案密铺性（个人觉得这个说法挺形象的）。由于上面提到的规则， \(1\) 的颜色是 \(1\) ，那么就可以继续推得质数的颜色是 \(2\) ，那么也就可以推得 \(3\) , \(4\) , \(5\) 的颜色归属。这样，每个颜色都尽可能铺满了所有能被染色的位置，知道不能再铺了才到下一个颜色。所以答案一定是最小的。（但是个人觉得这个证明不太严谨，欢迎各位大佬指正）。

做法也很简单，众所周知，线性筛可以求出每个数的最小质因子。而容易证明，次大因子就是原数除以最小质因子。所以我们只需跑线性筛一遍（注意细节，参见下面代码），然后按上面的步骤就行。时间复杂度 \(O(n)\) 。

还有另一种做法，就是证明答案对于 \(2\) 的次幂有可划分性。那样就直接取 \(2\) 的对数就行，时间复杂度也是 \(O(n)\) ，但代码实现更简单，只是更难想到。具体证明过程等我请教完再补充，昨天讲的现在有点忘了……

代码示例

方法一：次大因数法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m;
int val[N],prm[N];
int ans[N];
int main() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n;for(int i=2;i<=n;i++) {if(!val[i]) {val[i]=i;prm[++m]=i;}for(int j=1;j<=m;j++)if((ll)prm[j]*i<=(ll)n) val[prm[j]*i]=prm[j];}for(int i=1;i<=n;i++) {if(i==1) {ans[i]=1;continue;}ans[i]=ans[i/val[i]]+1;}for(int i=1;i<=n;i++) cout<<ans[i]<<' ';return 0;
}

方法二：对数法

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
int lg[N];
int main() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n;for(int i=1;i<=n;i++) {lg[i]=lg[i>>1]+1;cout<<lg[i]<<' ';}return 0;
}

这应该也是最详细的题解了吧