Tìm tất cả các số nguyên dương k sao cho các phần tử trong mảng a lấy phần dư với k đều bằng nhau

#1

đề bài:cho mảng số nguyên dương a[] gồm n số.tìm tất cả các số nguyên dương k sao cho các phần tử trong a[] lấy phần dư với k đều bằng nhau.Anh chị giúp em với ạ.Em cám ơn nhiều

#2

Bạn sử dụng 2 vòng for lồng nhau.
for1: cho k chạy từ 1 -> min của mảng a[]
Gán 1 biến phần dư = a[0] % k;
for2: cho i chạy từ 1 -> n
Bạn kiểm tra nếu có bất kỳ a[i] % k != phần dư thì break luôn,
nếu bằng thì tăng biến đếm lên 1.
Hết vòng for2: kiểm tra đếm có bằng n-1 không? có thì k chính là 1 giá trị k cần tìm, tiếp tục vòng for1 cho tới hết bạn sẽ thu được tất cả k.

3 Likes
#3

mình làm được rồi.cám ơn bạn nhé

#4

gcd(|a[i] - a[j]|) 0<i<j<n

3 Likes
#5

là sao vậy bạn.bạn nói rõ hơn được không

#6

@giang3: Lần sau nếu bạn đã làm được thì hãy đăng code/ý tưởng của bạn lên nữa, thay vì chỉ hỏi mỗi đề bài thôi nhé.

4 Likes
#8

xin lỗi nhưng mình không làm được ý. nhờ ý tưởng của bạn cmt trên thì mình làm được rồi

#10

lỡ n số trong a bằng nhau thì thế nào :V

3 Likes
#11

Nếu lỡ chọn a[i] = a[j] = a[k] thì d = a[i] :slight_smile:

3 Likes
#12

thì kq k = {1, 2, 3…a}

#13

Cách này hình như k chạy được với trường hợp n < 3, với trường hợp a[i] = a[j] | a[j] = a[k]

update: à. ok

Với bạn có thể giải thích giúp thuật toán: tại sao chọ d = gcd(|a[i] - a[j]|, |a[j] - a[k]|) k vậy? thanks

#14

Vì a[i] = a[j] (mod d) <=> a[i] - a[j] = 0 (mod d) <=> (a[i] - a[j]) chia hết cho d, vậy lấy ước chung lớn nhất của các hiệu để khởi tạo.

6 Likes
#15

ờ ha, bạn nói & thử mới thấy 2 cái này tương đương. Không ngờ hay vậy luôn (y)
thanks

#17

Để tìm gcd(|a[i] - a[j]|), 0 < i < j < n ta chỉ cần tìm gcd(|a[i+1] - a[i]|, i = 1..n-1, do d | k <=> d | (-k), tính kết hợp và tính chất gcd(a, b) = gcd(a, a+b).

4 Likes
#19

nma sao lại là ucln của hiệu mà không phải lấy ucln của dãy số luôn vậy

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