これのお話を書いてみます．
問題概要
素数 \(m\) と，要素数 \(n\) の数の集合 \(A\) が与えられる． 次の条件を満たす \(x\) および \(d\) が存在すればそれを出力せよ．
「この集合を並べ替えてできた長さ \(n\) の数列のうち，\(i\) 項めが \(x + (i-1)d \bmod{m}\) に一致するものが存在する」
法 \(m\) での等差数列となるように並べ替えられるなら，その数列の初項と公差を教えてね，という問題です．
Sample Input 1
17 5 0 2 4 13 15
Sample Output 1
13 2
13, 15, 0 (17), 2 (19), 4 (21) とすることができます．
方針
以下，法 \(m\) で考えます．
\(n = 1\) または \(n = m\) の場合は自明に作ることができるので，\(1 < n < m\) を考えます．
\(A\) の要素から \(x\) を決め打ちします．このとき，この数列の総和は \(xn + d\cdot n(n-1)/2\) です． ところで，これは \(\sum A\) と一致するはずですから，以下の式が成り立ちます．
\[ \sum A \equiv xn+d\cdot n(n-1)/2. \] すなわち， \[ d \equiv \left(\left(\sum A\right)-xn\right)\cdot(n(n-1)/2)^{-1}. \]
つまり，\(x\) を決め打ちすると \(d\) の候補は一意に定まることがわかりました．
\(d \equiv 0\) の場合は不適なので別の \(x\) を試します． そうでない場合，\(d\) と \(m\) は互いに素であることが言えます．
ところで，\(x-d\) が \(A\) に含まれている場合も不適と言えます． \(x-d \equiv x+(m -1)d\) であり，\(m\) 項めに現れるはずです．これは \(n < m\) に矛盾します．
そうでなければ，\(x+(i-1)d\) が \(A\) に含まれるかを各 \(i\) について調べます．
すべての \(x\in A\) についてこれを試し，条件を満たせばそれを出力し，見つからなければ不可能です．
提出結果
なんか通る．
\(x-d\) の枝刈りをしないと TLE になる．
解析
わからない，たすけて．
最悪ケースってどう構成できるんでしょう...？
