Code tìm số M sao cho các số trong mảng đồng dư mod M bị chạy quá thời gian với test lớn

#1

Mn giúp em cải thiện tốc độ code với ạ :frowning: em nghĩ nãy h chưa ra.

#include <bits/stdc++.h>
 typedef long long ll;
using namespace std;
bool kiemtra (ll a[], int n, int k)
  {
    int mod = a[0]%k;
    for (int i=1;i<n;i++)
       if (a[i]%k!=mod) return false;
    return true;
  }
int main() {
int n;
ll *a;
ifstream fi;
fi.open("game.inp");
fi >> n;
a = new ll[n];
for (int i=0;i<n;i++) fi >> a[i];
sort (a,a+n);
int j = 2;
ofstream fo("game.out");
while (j<=a[n-1])
  {
   if (kiemtra(a,n,j)) fo << j <<" ";
   j++;
  }
  delete[] a;
fo.close();
fi.close();
return 0;
}

Đề bài:

#3

em newbie chưa hiểu lắm anh giải thích cho em thêm đc không ạ

#4

B[i] cùng số dư với B[j] khi chia cho M => B[i] = B[j] (mod M) <=> B[i] - B[j] = 0 (mod M) <=> M | B[i] - B[j]

vậy M | UCLN(i,j < n)(B[i] - B[j]) (*)

KMTTQ xét i > j, đặt B'[i] = B[i+1] - B[i], ta có B'[j] + B'[j+1] + ... + B'[i] = B[i] - B[j].
Như vậy ta có M | UCLN(B'[j], B'[j+1], ..., B'[i], B[i] - B[j])
Áp dụng định nghĩa và tính chất kết hợp của UCLN, điều kiện cần và đủ là
M | UCLN(B'[0], B'[1], ..., B'[N-2]) ■

3 Likes
#5

M phải chia hết cho |Bi - Bj| bất kì chứ nhỉ :V Ví dụ 10 số thì có 45 hiệu như vậy :V Đề cho N tối đa 100 vậy có tối đa 4950 (100 chọn 2) hiệu |Bi - Bj|. Tìm ucln của 4950 hiệu này :V rồi tìm số ước của ucln này là ra.

3 Likes
#6

Đầu tiên ta có gcd(a, b, b) = gcd(a, b, a) = gcd(a, b) :smiley:

Mỗi hiệu B[i] - B[j] có thể được xây dựng từ một chuỗi B’ như sau:
■ ta có gcd(a, b) = gcd(a+b, b) nên

gcd(B'[0], B'[1]) = gcd(B[2] - B[0], B'[1])
gcd(B[2] - B[0], B'[2]) = gcd(B[3] - B[0], B'[2])
..................
gcd(B[n-2] - B[0], B'[n-1]) = gcd(B[n-1] - B[0], B'[n-1])

áp dụng định nghĩa và tính kết hợp thôi.

4 Likes
#7

mất công chứng minh thêm vài bước nữa, N nhỏ chạy trâu cho rồi :V :V

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?