AT_arc115_c 题解

· · 题解

一道构造题，带大家手推一下这个序列。

第一个位置：1 是所有正整数的因数且是最小的正整数，所以 1 是第一个数（还有一种方法，就是直接看样例输出，第一个是 1）。

第二个位置：一是二的因数，所以不能填 1，那就填其次小的，也就是 2（样例中第二个数也是 2）。

第三个位置：二不是三的因数，还是填 2（样例第三个数是 2）。

第四个位置：二是四的因数，往上加一，填 3（样例第三个数是 3）。

第五至七个位置：不是四的倍数，继续填 3。

第八个位置：四是八的因数，加一填 4。

第九到十五个位置：不是八的倍数，填 4。

剩下的不打了，规律也很明显了。第 j 个数出现 2^{j-1} 次。所以第 j 个数就是 \log(j)+1。