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