iterate it.cpp

#include <bits/stdc++.h>
#define abs(x) ((x) < 0 ? -(x) : (x))
#define uint unsigned int
using namespace std;

int gcd(int x, int y)
{
    if (x > y)
        swap(x, y);
    while (x > 0) {
        int z = x;
        x = y % x;
        y = z;
    }
    return y;
}

int main()
{
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> start(N);
    for (int i = 0; i < N; i++)
        cin >> start[i];            // primeira otimização
    set<int> su;                    // cria um set para eliminar repetidos e ordenar
    for (int i = 0; i < N; i++)     // ordenar bastaria, mas é ineficiente pois tem casos
        su.insert(start[i]);        // com muitos numeros repetidos
    start.clear();
    for (auto x : su)               // carrega tudo no vetor denovo, mas sem repetidos e ordenados
        start.push_back(x);
    N = start.size();
    int rep = 0;
    while (N > 0) {
        if (start[0] == 1 && rep > 0) {         // segunda otimização
            rep += start[N - 1];                // ao encontrar '1' no vetor as iterações seguintes serão sempre 
            break;                              // decrecidas de '1', logo da de encurtar o loop
        }
        vector<int> occ(start[N - 1] + 1, 0);
        for (int i = 0; i < N; i++)     // terceira otimização
            for (int j = 0; j < i; j++) // pode ser feito apenas metade dos testes, a outra tera os mesmo resultados
                if (start[i] != start[j])         // quarta otimização
                    occ[start[i] - start[j]] = 1; // em vez de salvar o resultado como valor, coloca no indices
        start.clear();                            // evitando repetidos
        int g = 0;                                        
        for (int i = 1; i < (int)occ.size(); i++)         // quinta otimização  
            if (occ[i])                                   // se todos possuem um divisor em comum
                g = gcd(g, i);                            // podemos computalo
        if (g > 0)                                        // e dividir todos os elementos por este divisor
            for (int i = g; i < (int)occ.size(); i += g)  // e garantir que se chege em '1' (ver linha 38)
                if (occ[i])                               // ao invez de ficar preso em outro multiplo
                    start.push_back(i / g);
        N = start.size();
        rep++;
    }
    cout << rep << "\n";
    return 0;
}