关于 ICPC 2022 沈阳 F 题的正确性证明

给没读过题的读者简要说一下，大致就是在一系列观察之后，题意会变为：给定一个正整数

n \le 10^6

，保证

n \bmod 4 = 0

或

n \bmod 4 = 3

，试构造一个数列，使得数列中所有数均为正整数，且它们的和等于

n

，平方和等于

\frac{n(n-1)}{2}

。

然后我的乱搞做法构造了出来。

CPP

int solve(long long req,int w)
{
    if(req<w) return 0;
    if(req==w)
    {
        while(req--) v.push_back(1);
        return w; 
    }
    long long sum=0;
    for(long long x=sqrt(req);x>0;x--)
    {
        v.push_back(x);
        sum=x+solve(req-x*x,w-x);
        if(sum==w) return sum;
        v.pop_back();
    }
    return sum;
}

官方题解则说，“每次取尽可能大的数即可”。

现在，我好奇的是，这个问题在

n

更大的时候仍然是有解的吗？如果是，怎么证明？以及怎么证明官方题解的构造是正确的？

关于 ICPC 2022 沈阳 F 题的正确性证明

讨论操作

回复

相关推荐

关于 ICPC 2022 沈阳 F 题的正确性证明