题解：AT_arc220_a [ARC220A] Sum of Reciprocals of Squares

ysw_2029 · 2026-05-19 09:32:30 · 题解

只会写 A，还是太菜了。

首先，我们注意力惊人的发现 \frac{1}{a^2}=\frac{1}{4a^2}+\frac{1}{4a^2}+\frac{1}{4a^2}+\frac{1}{4a^2}。也就是说，如果一个合法序列 A 中含有数字 a，则将这个数换为四个 2a 也是合法的。

注意到我们这样构造会使序列长度增加 3，也就是说，如果长度为 n 存在一种合法的构造，那么长度为 n+3 也存在一种合法的构造。 而且这是容易构造的。

显然 A=\{1\} 是合法的。所以所有 n\mod3=1 的数都是合法的。

随后我们再次注意力惊人的发现 \frac{1}{4}=\frac{1}{9}+\frac{1}{9}+\frac{1}{36}，也就是说 2 可以换为 3，3，6。

因为 A=\{2,2,2,2\} 是合法的，所以 A=\{2,2,2,3,3,6\} 和 A=\{2,2,3,3,3,3,6,6\} 也是合法的。而注意到这两个序列的长度 n\mod3 分别等于 0、2，所以我们只需要对模 3 的余数进行分讨即可。

至于构造方式，我们用优先队列存一下所有数，每次取出最小的数，将他删掉并往优先队列里加入四个这个数乘二的值。

似乎没有什么值得特别注意的地方。

:::success[AC code]

#include<bits/stdc++.h>
using namespace std;
int t,n;
priority_queue<int,vector<int>,greater<int> >q;
inline void work()noexcept
{
    cin>>n;
    if(n%3==0)
    {
        if(n<6)
        {
            puts("No");
            return;
        }
        q.push(2),q.push(2),q.push(2),q.push(3),q.push(3),q.push(6);
        puts("Yes");
        while(q.size()<n)
        {
            int x=q.top();
            q.pop();
            for(int i=1;i<=4;i++)q.push(x<<1);
        }
        while(!q.empty())
        {
            cout<<q.top()<<' ';
            q.pop();
        }
        cout<<endl;
        return;
    }
    if(n%3==1)
    {
        puts("Yes"),q.push(1);
        while(q.size()<n)
        {
            int x=q.top();
            q.pop();
            for(int i=1;i<=4;i++)q.push(x<<1);
        }
        while(!q.empty())
        {
            cout<<q.top()<<' ';
            q.pop();
        }
        cout<<endl;
        return;
    }
    if(n%3==2)
    {
        if(n<8)
        {
            puts("No");
            return;
        }
        puts("Yes");
        q.push(2),q.push(2),q.push(3),q.push(3),
        q.push(3),q.push(3),q.push(6),q.push(6);
        while(q.size()<n)
        {
            int x=q.top();
            q.pop();
            for(int i=1;i<=4;i++)q.push(x<<1);
        }
        while(!q.empty())
        {
            cout<<q.top()<<' ';
            q.pop();
        }
        cout<<endl;
        return;
    }
}
signed main()
{
    cin>>t;
    while(t--)work();
    return 0;
}

:::