読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #395 (Div. 1) C. Timofey and remoduling (modsqrt)

http://codeforces.com/contest/763/problem/C

解法

分散を使うことで公差が分かる。

V(a+bX)=b^2V(X) なので、等差数列 a,a+d,a+2d,\ldots,a+(n-1)d の分散は 0,1,2,\ldots,n-1 の分散に d^2 を掛けたものとなる。

よって

\begin{align}
d^2 = \frac{12V}{n^2-1}
\end{align}

公差が分かれば、適当に一点決めて±dずつずらして全ての値に到達できるかを判定すればいい。

mod 平方根に関しては以下の記事に書いておいた。

pekempey.hatenablog.com