E. Missing Numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Chouti is working on a strange math problem.
There was a sequence of nn positive integers x1,x2,…,xnx1,x2,…,xn, where nn is even. The sequence was very special, namely for every integer ttfrom 11 to nn, x1+x2+...+xtx1+x2+...+xt is a square of some integer number (that is, a perfect square).
Somehow, the numbers with odd indexes turned to be missing, so he is only aware of numbers on even positions, i.e. x2,x4,x6,…,xnx2,x4,x6,…,xn. The task for him is to restore the original sequence. Again, it's your turn to help him.
The problem setter might make mistakes, so there can be no possible sequence at all. If there are several possible sequences, you can output any.
Input
The first line contains an even number nn (2≤n≤1052≤n≤105).
The second line contains n2n2 positive integers x2,x4,…,xnx2,x4,…,xn (1≤xi≤2?1051≤xi≤2?105).
Output
If there are no possible sequence, print "No".
Otherwise, print "Yes" and then nn positive integers x1,x2,…,xnx1,x2,…,xn (1≤xi≤10131≤xi≤1013), where x2,x4,…,xnx2,x4,…,xn should be same as in input data. If there are multiple answers, print any.
Note, that the limit for xixi is larger than for input data. It can be proved that in case there is an answer, there must be a possible sequence satisfying 1≤xi≤10131≤xi≤1013.
Examples
input
Copy
6 5 11 44
output
Copy
Yes 4 5 16 11 64 44
input
Copy
2 9900
output
Copy
Yes 100 9900
input
Copy
6 314 1592 6535
output
Copy
No
Note
In the first example
- x1=4x1=4
- x1+x2=9x1+x2=9
- x1+x2+x3=25x1+x2+x3=25
- x1+x2+x3+x4=36x1+x2+x3+x4=36
- x1+x2+x3+x4+x5=100x1+x2+x3+x4+x5=100
- x1+x2+x3+x4+x5+x6=144x1+x2+x3+x4+x5+x6=144
All these numbers are perfect squares.
In the second example, x1=100x1=100, x1+x2=10000x1+x2=10000. They are all perfect squares. There're other answers possible. For example, x1=22500x1=22500 is another answer.
In the third example, it is possible to show, that no such sequence exists.
题意：
给出偶数位置的数，让你求奇数位置的数，并且任意的前缀和都满足完全平方数
思路：
设现在我们有前3项已经完成，并且他们的和是sum，后一个的偶数位置为y，奇数位置为x
sum肯定是完全平方数，y + sum 和 x + y + sum也是，设a = sqrt(x + y + sum)，b = sqrt(y + sum)
所以a^2 - b^2 = y
(a + b) * (a - b) = y
(a + b) 和 (a - b)就是y的两个因子
稍微化简可以得：
(a + b) = y / (a - b)
设(a + b) = y1
a + b = y1
a - b = y / y1
2a = y1 + y / y1
2b = y1 - y / y1
那么就可以枚举y的因子，并且a - b>0，我们要使得x最小，即a最小，每次取min
代码：
bool check(ll x){if(sqrt(x) * sqrt(x) == x) return true;return false;
}
int main(){ios::sync_with_stdio(false);
// wt(sqrt(0));cin >> n;for(int i = 1;i <= n / 2;i++) cin >> a[i];vector<ll>ans;ll sum = 0;for(int i = 1;i <= n / 2;i++){ll y = a[i],flag = 0,Min = 1e18;for(ll j = 1;j * j <= y;j++){if(y % j == 0){int y1 = j,y2 = y / j;if(abs(y1 - y2) % 2 == 0){ll c = (y1 + y2) / 2;ll s = c * c; s -= sum,s -= y;if(s > 0)Min = min(s,Min),flag = 1;}}}if(!flag){wt("No");return 0;}else{ans.pb(Min);ans.pb(a[i]);sum += a[i];sum += Min;}}wt("Yes");for(auto d:ans){cout << d << " ";}cout << endl;return 0;
}