AT_arc115_c题解

Fa_Nanf1204 · 2023-12-27 14:40:41 · 题解

算法思路：数学

分析

这题代码不难，主要是思路。我们可以手推一下这个序列情况。

要求每个数最小，那么 A_1 取数字 1，因为 1 是所有数字的因数且最小。

再看 A_2，A_2 不能与 A_1 相等，所以取尽可能小的 2。

再看 A_3，可以取 2。

再看 A_4，A_4 不能与 A_1 和 A_2 相等，所以取尽可能小的 3。

以此类推。

扩展这个序列，可以得到：1\;2\;2\;3\;3\;3\;3\;4\;4\;4\;4\;4\;4\;4\;4。

结论

可以得出结论：数字 i 在序列中出现了 2^{i-1} 次。

代码

#include<bits/stdc++.h>
using namespace std;
int n,cnt=0,j=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        j++;//计数当前数出现了几次 
        if (j<=pow(2,cnt)){//判断数量是否符合要求 
            cout<<cnt+1<<" ";//输出 
        }
        else{
            j=1;//重新计数 
            cnt++;
            cout<<cnt+1<<" ";//输出 
        }
    }
    return 0;
}