Работа с массивами С++

372

22 января 2017, 15:23

Дано массив A размером N (1 < N < 10^ 9). Найти такое максимальное К, что А[i] % k = A[j] % k , для всех {i,j}. Каким быстрым алгоритмом можно это реализовать? Кроме алгоритма обычного перебора можно искать разность элементов, а потом их минимальный НОД. Но этот метод также слишком длинный.

Answer 1

Собирая воедино комментарии @KoVadim и @VladD - что-то вроде

template<typename T, typename = std::enable_if_t<std::is_integral<T>::value>>
T gcd(T m, T n)
{
    while(m && n) if (m < n) n %= m; else m %= n;
    return (m == T(0)) ? n : m;
}
int main(int argc, const char * argv[])
{
    constexpr int delta = 46574;
    constexpr int rem   =  2563;
    vector<long long> v;
    v.reserve(100000);
    for(int i = 0; i < 100000; ++i)
    {
        v.push_back(rand()*delta + rem);
    }
    long long dif = abs(v[1] - v[0]);
    for(int i = 2; i < 100000; ++i)
    {
        long long d2 = abs(v[i] - v[i-1]);
        dif = gcd(dif,d2);
        if (dif == 1) break;
    }
    cout << dif << endl;
}