acm吧 关注：26,418贴子：48,062
- 5回复贴，共1页
提供一种divE不同与Editorial的做法（来源于quality)
检查所有的d=a[i]-a[1]，并用d和sum求出首项tmp,再求出所有项的平方和ret, 与原来输入的数平方和比较，若相同，则用d和tmp求出所有的项，并check, 若成功，则输出d和tmp, 总共check次数不超过2次
In order to meet the conditions for which this algorithm can work, we consider only p which is odd and n<m-1. While there is no deterministic way for solving an arbitrary quadratic equation, it can easily be transformed into y^2 = d (mod p) where the Cipolla algorithm allows us to solve with approximately 1/2 probability for each random number. So, the expected value is 2. The overall complexity is O(n log n + k log p), where k is the number of tries in the Cipolla algorithm. It can be quite high for the problem conditions, so although there is a probability for failure, it is very small.（gsCEA）
Nice solution! And in fact, you can simply try all a[i]-a[1] as d and find x with x+(x+d)+...+(x+(n-1)d) equals to the sum of the elements. As you have said, there are at most two pairs (x,d) which satisfy x^2+(x+d)^2+...+(x+(n-1)d)^2 equals to the sum of square. So we can check these two pairs by brute force.（quailty）
（若有错误轻喷）
检查所有的d=a[i]-a[1]，并用d和sum求出首项tmp,再求出所有项的平方和ret, 与原来输入的数平方和比较，若相同，则用d和tmp求出所有的项，并check, 若成功，则输出d和tmp, 总共check次数不超过2次
In order to meet the conditions for which this algorithm can work, we consider only p which is odd and n<m-1. While there is no deterministic way for solving an arbitrary quadratic equation, it can easily be transformed into y^2 = d (mod p) where the Cipolla algorithm allows us to solve with approximately 1/2 probability for each random number. So, the expected value is 2. The overall complexity is O(n log n + k log p), where k is the number of tries in the Cipolla algorithm. It can be quite high for the problem conditions, so although there is a probability for failure, it is very small.（gsCEA）
Nice solution! And in fact, you can simply try all a[i]-a[1] as d and find x with x+(x+d)+...+(x+(n-1)d) equals to the sum of the elements. As you have said, there are at most two pairs (x,d) which satisfy x^2+(x+d)^2+...+(x+(n-1)d)^2 equals to the sum of square. So we can check these two pairs by brute force.（quailty）
（若有错误轻喷）
