[ARC115C] ℕ Coloring题解

lgydkkyd · 2023-12-30 22:38:35 · 题解

这是一道构造题，题目让我们构造一个序列使得任意一个位置的数与其因数位置上的数不等，且尽量要小。接下来分析一下，首先因为 1 是所有的正整数的因子之一，所以一定要把 1 放在最前面，再推第 2 个数，由于 1 是 2 的因子，则第 2 个数不能是 1，那就取正整数中第 2 小的数，也就是 2，接下推第 3 个数，由于 1 是 3 的因子，则第 3 个数不能为 1，同样取 2，后面的书都可以以此类推。最后推出的序列为 1，2，2，3，3，3，3，4，4，4，4，4，4，4，4 等等。也就是 x 在序列中出现了 2 的 x-1 次。说刚好每个数都可以用函数计算，请看代码。

Code

#include<bits/stdc++.h>
using namespace std;
inline void read(int &a){//快读
    a=0;
    char c;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') a=a*10+c-'0',c=getchar();
}
inline void write(int a){//快写
    if(a>9)write(a/10);
    putchar(a%10+'0');
}
int n;
int main(){
    read(n);
    for(int i=1;i<=n;i++){
        write(int(log2(i)+1));//这就是上文说的函数log,第i个数就是log2(i)+1,可以直接输出
        printf(" ");//每输出一个数都要加上空格
    }
    return 0;//华丽结束~~~
}