Codeforces 1081 E

传送门

题目大意

给定长度为 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]);
	}
}
上一篇:PTA basic 1081 检查密码 (15 分) c++语言实现(g++)


下一篇:1081 检查密码 (15分)