Round 1C 2022 - Code jam 2022 b.square (Mathematics, thinking)

subject

T(T<=100) Group example , Every time given n(n<=1000) Number , The first i Number ei(-1000<=ei<=1000),

You need to add up to k individual [-1e18,1e18] Range of integers ,

Make this n+k The sum of squares of numbers is equal to the square of sum , namely

If by no means equal , Output IMPOSSIBLE

Small scale ：k=1

large-scale ：k<=1000

Source of ideas

Official explanation

Answer key

consider k=1 What to do when , Set the number to be added as x, Shift out x Value ,

,

That is to say by n The number and , by n Sum of squares of numbers , 

stay k>1 when , The denominator 2*sum Inspire us , Try to make new and by 1,

You need to fill one first Value ,

Corresponding new sum of squares

That is to say ,

be aware It's odd , Show the current n+1 There are odd numbers among them ,

Then the sum of squares must also be odd , namely Must be an even number , Must be an integer

This shows that ,k>1 There must be a solution , And add two numbers 、 that will do

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int t,n,k;
ll a[N];
int main(){
    scanf("%d",&t);
    for(int ca=1;ca<=t;++ca){
        scanf("%d%d",&n,&k);
        ll sum=0,sum2=0,ans;
        printf("Case #%d: ",ca);
        for(int i=1;i<=n;++i){
            scanf("%lld",&a[i]);
            sum+=a[i];sum2+=a[i]*a[i];
        }
        if(k>=2){
            sum2+=1ll*(1-sum)*(1-sum);
            printf("%lld ",1-sum);
            sum=1;
        }
        if(!sum){
            if(sum*sum==sum2){
                puts("0");
            }
            else{
                puts("IMPOSSIBLE");
            }
            continue;
        }
        if((sum2-sum*sum)%(2ll*sum)){
            puts("IMPOSSIBLE");
        }
        else{
            ans=(sum2-sum*sum)/(2ll*sum);
            printf("%lld\n",ans);
        }
    }
    return 0;
}