传送门

题目大意

给定长度为 n n n（ n n n为偶数）的数列 x x x的偶数项，求出数列 x x x的奇数项，使得对于任意 t ∈ [ 1 , n ] ， x 1 + x 2 + . . . + x t t∈[1,n]，x1+x2+...+xt t∈[1,n]，x1+x2+...+xt为平方数，若无解输出 N o No No，否则先输出一行 Y e s Yes Yes，再输出 x 1 , x 2 , x 3 , . . . , x n x1,x2,x3,...,xn x1,x2,x3,...,xn，若有多解输出任意一组解。
x x x数组奇数项不超过 1 0 13 10^{13} 1013，偶数项不超过 1 0 5 10^5 105, n < = 1 0 5 n<=10^5 n<=105。

思路

一边计算一边维护前缀和
差分序列中的一项 c c c，必定要满足有 a 2 − b 2 = c a^2−b^2=c a2−b2=c，即 ( a − b ) × ( a + b ) = c (a−b)×(a+b)=c (a−b)×(a+b)=c，那么现在已知 c c c
把 c c c因式分解，使 ( a − b ) , ( a + b ) (a−b),(a+b) (a−b),(a+b)为 c c c的一对因子。
设其中一个因子为 x x x，不妨设x为一对之中大的那个因子，那么令 a + b = x , a − b = c / x a+b=x,a−b=c/x a+b=x,a−b=c/x联立两式可解得， 2 a = x + c / x , 2 b = x − c / x 2a=x+c/x,2b=x−c/x 2a=x+c/x,2b=x−c/x。那么 a ， b a，b a，b存在的充分必要条件就是这对因子和（差）为偶数。
针对每个数，我们都选择构造尽量小的平方数，这样保证在之后的构造中能够有更多的选择。在构造当前数的选择上，已经有的前缀和为now，那么当前数就为 a n s − n o w ans−now ans−now。

代码

int n;
int q=0;
ll a[maxn],b[maxn];
ll now;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n/2;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n/2;i++){
		ll tmp,ans=1e15;
		for(int j=1;j*j<=a[i];j++){
			if(a[i]%j) continue;
			ll xx=j,yy=a[i]/j;
			if((xx-yy)%2)continue;
			tmp=(xx-yy)*(xx-yy)/4;
			if(tmp>now)ans=min(ans,tmp);
		}
		if(ans==1e15){
			puts("No");
			return 0;
		}
		b[++q]=ans-now;
		b[++q]=a[i];
		now=a[i]+ans;
	}
	puts("Yes");
	for(int i=1;i<=n;i++){
		printf("%lld ",b[i]);
	}
}