posta

Algoritmul, pas cu pas

1. Casele vizitate sunt exact numerele de forma $1 + k \cdot x$, adică numerele $m$ cu $m - 1$ multiplu de $x$.
2. Casa $a_i$ e vizitată $\iff x \mid (a_i - 1)$.
3. Ca să fie vizitate toate casele, $x$ trebuie să dividă fiecare $a_i - 1$. Cel mai mare astfel de divizor comun e $\text{cmmdc}(a_1 - 1, a_2 - 1, \dots, a_n - 1)$.
4. Îl acumulez cu algoritmul lui Euclid: pornesc cu $g = 0$ (cmmdc cu $0$ dă celălalt număr) și fac $g = \text{cmmdc}(g, a_i - 1)$.

Complexitate: $O(n \cdot \log(\max a_i))$.

Soluția în C++

#include <fstream>
using namespace std;

ifstream fin("posta.in");
ofstream fout("posta.out");

long long cmmdc(long long a, long long b) {
    while (b) { long long r = a % b; a = b; b = r; }
    return a;
}

int main() {
    int n;
    fin >> n;
    long long g = 0, a;
    for (int i = 0; i < n; i++) {
        fin >> a;
        g = cmmdc(g, a - 1); // x trebuie să dividă a-1 pentru fiecare casă
    }
    fout << g << "\n";
    return 0;
}