题解 CF1850E Cardboard for Pictures

cjh20090318 · 2023-07-23 08:26:58 · 题解

题意

给你 n 个整数 s 和一个整数 c，你需要找到一个整数 w 满足 \sum\limits_{i=1}^n(2w+s_i)^2=c。

分析

很显然这是一个一元二次方程。

将上式根据完全平方公式化简可以得到，我们要求的方程是：

移项又可以得到：

所以直接用求根公式可以解得：

注意事项

可能需要用到 __int128，需要使用 C++20，并且需要手写 sqrt 函数。（但是 long double 强转好像也可以过）。

代码

//the code is from chenjh
#include<cstdio>
typedef long long LL;
int n;LL c;
__int128 mySqrt(__int128 x){if(!x)return 0;__int128 left=1;__int128 right=x>>1;while(left<right){__int128 mid=(right+left)/2+1;if(mid>x/mid) right=mid-1;else left=mid;}return(__int128)left;}//手写二分 sqrt。
void solve(){
    scanf("%d%lld",&n,&c);
    LL A=(n<<2),B=0,C=0;//一元二次方程的三个系数。
    for(int i=1,s;i<=n;i++){
        scanf("%d",&s);
        B+=s,C+=s*s;
    }
    B<<=2ll;
    printf("%lld\n",LL((-B+mySqrt((__int128)B*B-(__int128)4*A*(C-c)))/2/A));//根据求根方程求解。
}
int main(){
    int T;scanf("%d",&T);
    while(T--) solve(); 
    return 0;
}