AtCoder Regular Contest 163

C - Harmonic Mean

题意

要求构造一个长度为 $n$ 的一个数组 $a$，满足以下条件：

• $\sum\limits_{i=1}^n\dfrac{1}{a_i}=1$
• $a$ 中的元素各不相同
• $1\leq a_i\leq 10^9$

题解

利用 $\dfrac{1}{k(k+1)}=\dfrac{1}{k}-\dfrac{1}{k+1}$ 可以进行构造：$\dfrac{1}{1\times 2},\dfrac{1}{2\times3},\cdots\dfrac{1}{(n-1)\times n},\dfrac{1}{n}$。但是，$\dfrac{1}{n}$ 有可能和前面某一项重复，即 $n=k\times (k+1)$。

此时，我们构造 $a=(2,2a_1',2a_2',\cdots,2a_{n-1}')$，其中 $a_i'$ 为 $n-1$ 时的解，容易验证它是符合限制的。

可能会有人问为什么不直接都采取第二种构造方式。原因是它的增长速度太快，会超出 $10^9$ 的范围。而能表示成 $k\times (k+1)$ 的数是不连续的，所以上述构造方式可以保证 $a_i$ 在限制范围内。

代码

#include <bits/stdc++.h>
using namespace std;
vector<int> v[505];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int i=3;i<=500;i++)
    {
        bool ok=1;
        for(int k=1;k<i;k++)
        {
            v[i].push_back(k*(k+1));
                if(i==k*(k+1)) ok=0;
        }
        if(ok) v[i].push_back(i);
        else
        {
            v[i].clear();
            v[i].push_back(2);
            for(int k=0;k<i-1;k++) v[i].push_back(2*v[i-1][k]);
        }
    }
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        if(n==1) 
        {
            cout<<"Yes"<<'\n';
            cout<<1<<'\n';
        }
        else if(n==2) cout<<"No"<<'\n';
        else
        {
            cout<<"Yes"<<'\n';
            for(int i=0;i<n;i++) cout<<v[n][i]<<" \n"[i==n-1];
        }
    }
    return 0;
}