CF#538 E. Arithmetic Progression

Problem　https://codeforces.com/contest/1114/problem/E
Solution　https://codeforces.com/blog/entry/65136

We can find a[0]. Generating random values between 0 and n-1, then d=gcd(a[r[0]] - a[0], a[r[1]] - a[0], ... , a[r[29]] - a[0]) become the answer with high probability. Let's analyze it. If it doesn't give the answer, r[0],...,r[29] are a multiple of certain integer. The event that r[0], ... , r[29] are multiples of d, denote A[d], the fail probability is bounded by

\begin{align}
P(A_2 \cup A_3 \cup A_4 \cup A_5 \cup \cdots ) &\le P(A_2)+P(A_3)+P(A_4)+P(A_5)+\cdots \\
&\le \frac{1}{2^{29}} + \frac{1}{3^{29}} + \frac{1}{4^{29}} + \frac{1}{5^{29}} + \cdots \\
&= \zeta(29)-1 \\
&\le 1.8627 \times 10^{-9}
\end{align}

For simplicity, the first term is not picked. The reason not 30 but 29 is for removing this assumption. We can also bound by the integration.

\[ \bigcirc \le \frac{1}{2^{29}} + \int_{2}^{\infty} \frac{dx}{x^{29}} \le \frac{1}{2^{28}} \]