Tìm số d lớn nhất để a % d = b % d = c % d

Nguồn: Câu hỏi trong nhóm lập trình Độ khó: Trung bình Số học Ước chung lớn nhất Chia lấy dư

Đề bài

Mô tả

Hai bạn Hồng và Chi thường xuyên nhắn tin cho nhau. Một lần, Hồng muốn gửi thông tin là ba số nguyên dương phân biệt $a, b, c$ cho Chi. Để chắc chắn Chi nhận được đúng ba số $a, b, c$, Hồng quyết định gửi thêm một số nguyên $d$ để Chi kiểm tra khi nhận được ba số $a, b, c$. Số nguyên $d$ mà Hồng chọn thỏa mãn điều kiện:

• $a \% d = b \% d = c \% d$, trong đó $\%$ là phép toán chia lấy dư;
• $d$ lớn nhất.

Cho ba số nguyên dương $a, b, c$ đôi một khác nhau, hãy giúp Hồng tìm số nguyên $d$ thỏa mãn yêu cầu trên.

Dữ liệu vào: Gồm một dòng chứa ba số nguyên dương $a, b, c$.

Dữ liệu ra: Ghi ra một số nguyên duy nhất là số $d$ tìm được.

Subtasks:

• Subtask 1 (50%): $a, b, c \le 10^6$;
• Subtask 2 (50%): $a, b, c \le 10^{18}$.

Ví dụ dữ liệu vào

3 5 7

Ví dụ dữ liệu ra

2

Lời mở đầu

Bữa giờ LeetCode hoài sợ anh em ngán 😅. Nay mình đi comment dạo thấy một bạn hỏi bài này cũng hay nên đăng để anh em thử sức nhé. Bạn ấy kể: "ý tưởng của em là tìm ra số nhỏ nhất trong 3 số (gọi là x), rồi cho i chạy từ x tới 1 để tìm giá trị i sao cho a%i==b%i==c%i… thuật toán của em bị chạy quá thời gian với các số lớn, còn nếu a, b, c là các số nhỏ thì vẫn đúng ạ". Thật ra cách đó không chỉ bị quá thời gian mà còn sai ở một số test nữa, mình sẽ chỉ ra ngay bên dưới. Bài này chỉ cần một nhận xét toán học nhỏ là ra lời giải siêu gọn. Hy vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ cho bạn nào chưa hiểu đề: với $a = 3, b = 5, c = 7$, thử từng $d$:

d	3 % d	5 % d	7 % d	Bằng nhau?
7	3	5	0	Không
6	3	5	1	Không
5	3	0	2	Không
4	3	1	3	Không
3	0	2	1	Không
2	1	1	1	Có ✅

Và mọi $d \gt 7$ thì phần dư chính là $3, 5, 7$, khác nhau. Vậy $d$ lớn nhất là 2.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Thử d từ max(a, b, c) về 1 · 50%Cách 2UCLN của các hiệu · O(log) · 100%

Cách 1Thử mọi d từ lớn về nhỏ – O(max(a, b, c))

Trước hết mình góp ý cho ý tưởng của bạn hỏi bài: cho $d$ chạy từ số nhỏ nhất trong 3 số về 1 là chưa đúng, vì $d$ hoàn toàn có thể lớn hơn số nhỏ nhất. Ví dụ $a = 1, b = 4, c = 7$: số nhỏ nhất là $1$ nên cách đó in ra $1$, nhưng $1 \% 3 = 4 \% 3 = 7 \% 3 = 1$, nên đáp án đúng là $d = 3$.

Vậy $d$ có thể lớn tới đâu? Nếu $d \gt \max(a, b, c)$ thì $a \% d = a$, $b \% d = b$, $c \% d = c$, mà 3 số này đôi một khác nhau ⇒ không thỏa. Nên chỉ cần thử $d$ từ $\max(a, b, c)$ giảm dần về $1$, gặp $d$ đầu tiên thỏa thì in ra và dừng luôn (vì đang đi từ lớn về nhỏ nên đó là $d$ lớn nhất). Vòng lặp chắc chắn dừng vì $d = 1$ luôn thỏa (mọi số chia 1 đều dư 0).

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long a, b, c;
    cin >> a >> b >> c;
    long long mx = max(a, max(b, c));
    for(long long d = mx; d >= 1; d--){
        if(a % d == b % d && b % d == c % d){
            cout << d;
            return 0;
        }
    }
    return 0;
}

a, b, c = map(int, input().split())
mx = max(a, b, c)
d = mx
while d >= 1:
    if a % d == b % d == c % d:
        print(d)
        break
    d -= 1

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$.
• Thời gian: xấu nhất phải thử hết từ $\max(a, b, c)$ về $1$ ⇒ $O(\max(a, b, c))$.

Không gian$O(1)$

Thời gian$O(\max(a, b, c))$

Chỉ được 50% điểm

Với subtask 1 ($\le 10^6$) thì chạy tức thì. Nhưng subtask 2 có số tới $10^{18}$ thì vòng lặp có thể chạy $10^{18}$ lần ⇒ TLE. Đây cũng chính là lý do bài của bạn hỏi bài bị quá thời gian.

Cách 2Đưa về ước chung lớn nhất của các hiệu – O(log)

Mấu chốt nằm ở một tính chất rất quen thuộc của phép chia lấy dư:

Nhận xét then chốt

$a \% d = b \% d \iff (a - b)$ chia hết cho $d$.
Chứng minh: viết $a = q_1 d + r_1$, $b = q_2 d + r_2$ với $0 \le r_1, r_2 \lt d$. Khi đó $a - b = (q_1 - q_2) d + (r_1 - r_2)$, mà $|r_1 - r_2| \lt d$, nên $a - b$ chia hết cho $d$ khi và chỉ khi $r_1 - r_2 = 0$, tức $r_1 = r_2$.

Áp dụng cho cả 3 số: $a \% d = b \% d = c \% d$ khi và chỉ khi $d$ là ước chung của $|a - b|$ và $|b - c|$ (còn $|a - c|$ thì tự động chia hết cho $d$ vì $a - c = (a - b) + (b - c)$). Mà đề muốn $d$ lớn nhất ⇒

Công thức

$d = \gcd(|a - b|,\ |b - c|)$

Thử lại với ví dụ: $\gcd(|3 - 5|, |5 - 7|) = \gcd(2, 2) = 2$ ✅. Với $1, 4, 7$: $\gcd(3, 3) = 3$ ✅. Vì $a, b, c$ đôi một khác nhau nên các hiệu đều khác $0$, đáp án luôn là số nguyên dương.

Còn ước chung lớn nhất thì tính bằng thuật toán Euclid: $\gcd(x, y) = \gcd(y, x \% y)$, lặp đến khi $y = 0$ thì $x$ chính là đáp án. Mỗi 2 bước số giảm ít nhất một nửa nên chỉ mất $O(\log)$ bước, với số tới $10^{18}$ cũng chỉ vài chục bước 😎.

Minh hoạ

Các bạn nhập $a, b, c$ (nhỏ thôi để vẽ được) rồi bấm Tiếp để xem cách tính hai hiệu, chạy Euclid, và cuối cùng thấy 3 số khi chia thành từng khối $d$ ô (xanh/tím xen kẽ) thì phần dư (màu cam) dài bằng nhau:

a b c

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này (mình tự viết hàm ucln bằng Euclid cho các bạn dễ hình dung; trong C++17 có thể dùng luôn __gcd hoặc std::gcd, Python có math.gcd):

#include <bits/stdc++.h>
using namespace std;

long long ucln(long long x, long long y){
    while(y != 0){
        long long r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int main(){
    long long a, b, c;
    cin >> a >> b >> c;
    long long x = abs(a - b);
    long long y = abs(b - c);
    cout << ucln(x, y);
    return 0;
}

def ucln(x, y):
    while y != 0:
        r = x % y
        x = y
        y = r
    return x


a, b, c = map(int, input().split())
x = abs(a - b)
y = abs(b - c)
print(ucln(x, y))

C++▶ Chạy tay từng dòng codeCách 2: x = |a − b|, y = |b − c|, rồi Euclid tính ucln(x, y).

Dữ liệu vào (stdin) – sửa thoải mái3 5 7

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4long long ucln(long long x, long long y){

5 while(y != 0){

6 long long r = x % y;

7 x = y;

8 y = r;

9 }

10 return x;

11}

12

13int main(){

14 long long a, b, c;

15 cin >> a >> b >> c;

16 long long x = abs(a - b);

17 long long y = abs(b - c);

18 cout << ucln(x, y);

19 return 0;

20}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$.
• Thời gian: thuật toán Euclid chạy $O(\log(\max(a, b, c)))$ bước, với $10^{18}$ thì chưa tới 100 bước.

Không gian$O(1)$

Thời gian$O(\log \max(a, b, c))$

Nhớ dùng long long

Số tới $10^{18}$ vượt xa giới hạn của int (khoảng $2 \cdot 10^9$), nên $a, b, c$ và các hiệu phải là long long. Hiệu $|a - b| \lt 10^{18}$ vẫn nằm gọn trong long long (tối đa khoảng $9.2 \cdot 10^{18}$) nên không lo tràn.

Ghi chú của mình: code C++ và Python của cả 2 cách cho đúng output ví dụ của đề, và đã được kiểm tra với 400 bộ test ngẫu nhiên nhỏ (số tới 300), so với một chương trình vét cạn thử mọi $d$ – khớp hết. Cách 2 còn được thử thêm với khoảng 300 bộ số ngẫu nhiên tới $10^{18}$ (có cả các bộ cố tình có ước chung lớn), so với math.gcd của Python – khớp hết và chạy tức thì. Với $a, b, c \le 10^6$ cách 1 chạy dưới 0.01 giây (C++) và khoảng 0.25 giây (Python).

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇