Xmas Contest 2017 H問題 Ango 解説

問題 | 解説まとめ

リアクティブ・encode/decode系の変わった問題。
部分点はmax(x)に関する関数にしてもよかったかなぁ。

部分点1

割と効率が悪くてもACできますがそこまで簡単ではないと思います。
例えばNが小さければフィボナッチ数列でいけますが、N=300だと厳しいです。
解答例としては、xを乱数にしたり、和が被らないようなxを愚直に探索するなどがあります。
N=300なら2つ選んだ時の和というのはあらかじめ列挙できるのでクエリに答えるのはあまり難しくありません。

部分点2

xは乱数でもおそらく被らないと思いますが、Nが大きいのでクエリへの応答が困難です。
ここで、(a^2+b^2)と(a+b)さえ分かっていれば a も b も求まるということを唐突に思いつきます。(そもそも僕が数日悩んだのち唐突に思いついたため、こうとしか解説できず)
S=(a^2+b^2), T=(a+b)として、ab=(T^2-S)/2が求まり、|x-y|=sqrt(S-2ab)が求まり、T+(a-b),T-(a-b)として a, b が求まります)
これを実現するにはGETA=500000などとしてx_i = i^2*GETA+iなどとしておけば、S=sum/GETA, T=sum\%GETAとして S, T が求められます。

部分点3

p=900001などとして、全ての演算の法をpとして計算します。
mod計算で難しい部分はsqrtですが、今回は1~400000についての二乗mod pの値を前計算しておけば十分です。(効率的に計算したい人はこちらを)
ちなみにsqrt(x) mod pの値は一意に定まらず2つありますが、正負が違うだけなのでどちらでも良いです。