granica.cpp

Bài toán

Tìm tất cả các số k sao cho tất cả n số đều đồng dư trên mô đun k.

Độ phức tạp

O(n^2 logn + sqrt(max(k)))

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <vector>

#include <algorithm>

using namespace std;

int n;

int a[1230997];

vector<int> T;

main(){

    int i, j, GCD=0;

    scanf("%d", &n);

    for (i=1; i<=n; i++)

    scanf("%d", &a[i]);

    for (i=1; i<=n-1; i++)

    for (j=i+1; j<=n; j++)

    GCD = __gcd(GCD, abs(a[i]-a[j]));

    T.push_back(GCD);

    for (i=2; i*i<=GCD; i++)

    if (GCD%i==0) {

        T.push_back(i);

        if (i*i!=GCD)

        T.push_back(GCD/i);

    }

    sort(T.begin(), T.end());

    for (vector<int> :: iterator it=T.begin(); it!=T.end(); it++)

    printf("%d ", *it);

    printf("\n");

}

Nhận xét

Ta chỉ cần tìm số k lớn nhất thỏa mãn đề bài, các số còn lại là ước của số k lớn nhất. Các số đồng dư với nhau theo mô đun k nên hiệu của từng cặp đôi một các phần tử phải chia hết cho k. Vậy nên số k lớn nhất là UCLN của tất cả các hiệu này.

Mô tả

Các lỗi thường gặp