Chia Quà (CHIAQUA)

Nguồn: VinhDinhCoder Độ khó: Dễ Số học Ước số Đếm ước

Đề bài

CHIAQUA – CHIA QUÀ · Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 128 megabyte

Trường THPT A chia quà cho học sinh cuối năm 2020, có $X$ chiếc áo và $Y$ hộp bánh. Phương án chia quà là chọn ra $N$ học sinh sao cho số áo và số hộp bánh có thể chia đều cho $N$ học sinh này mà không dư lại cái nào, đồng thời các học sinh sẽ nhận số lượng quà như nhau.

Yêu cầu: Tìm tất cả phương án chia quà thoả mãn điều kiện trên. Giả sử rằng số học sinh của trường là đủ để thực hiện tất cả phương án chia quà.

Dữ liệu nhập: Gồm hai số nguyên dương $X$ và $Y$ $(X, Y \le 10^9)$.

Kết quả: In ra một số duy nhất là kết quả tìm được.

Ví dụ – input

8 12

Ví dụ – output

3

Giải thích:

• Phương án 1: chọn ra 1 học sinh: mỗi em sẽ nhận 8 áo và 12 hộp bánh.
• Phương án 2: chọn ra 2 học sinh: mỗi em sẽ nhận 4 áo và 6 hộp bánh.
• Phương án 3: chọn ra 4 học sinh: mỗi em sẽ nhận 2 áo và 3 hộp bánh.

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

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

Nhắc lại ngưỡng quen thuộc: với giới hạn 1 giây thì toàn bài chỉ nên lặp khoảng $(3 \div 5) \cdot 10^7$ lần (C/C++) là an toàn, $10^8$ thì hên xui; Python, C#, Java chạy chậm hơn thì ngưỡng còn phải thấp hơn nữa. Bài này cho đúng 1 giây nên cứ canh theo ngưỡng đó.

Theo đề, cần chọn $N$ học sinh sao cho chia đều được $X$ chiếc áo và $Y$ hộp bánh. "Chia đều" ở đây tức là chia hết, không bị dư. Nghĩa là $N$ phải là ước của cả $X$ và $Y$ thì $X$ và $Y$ mới chia hết cho $N$ được. Đây là mấu chốt quan trọng ta phải nhìn ra.

Bài toán quy về

Đếm xem $X$ và $Y$ có bao nhiêu ước số chung. Như ví dụ $X = 8$, $Y = 12$: các ước chung là $1, 2, 4$ ⇒ có 3 ước chung ⇒ đáp án 3.

Số	Các ước
8	1, 2, 4, 8
12	1, 2, 3, 4, 6, 12

Để giải được bài này, các bạn cần biết qua các cách đếm số lượng ước của một số, vì nó được ứng dụng trực tiếp ở đây. Có 4 cách tối ưu dần lên: duyệt hết $1 \to N$ – $O(N)$, duyệt tới $N/2$ – $O(N/2)$, duyệt tới $\sqrt{N}$ – $O(\sqrt{N})$, và phân tích thừa số nguyên tố rồi dùng công thức. Cách 4 tuy nhanh nhất nhưng không áp dụng trực tiếp được ở đây, vì nó chỉ đếm ra có bao nhiêu ước chứ không liệt kê ra cụ thể từng ước. Trong bài này ta cần liệt kê từng ước của $X$, rồi với mỗi ước kiểm tra xem $Y$ có chia hết cho nó không (tức nó có là ước của $Y$ luôn không), thỏa thì tăng biến đếm.

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

Cách 1Duyệt mọi i từ 1 đến min(X, Y) – TLECách 2Duyệt ước theo cặp đến √min(X, Y)

Cách 1Duyệt mọi số từ 1 đến min(X, Y) – O(min(X, Y))

Cách "làm theo định nghĩa": thử mọi $i$ từ 1 đến $\min(X, Y)$ (ước chung không thể lớn hơn số nhỏ hơn), số nào mà cả $X$ và $Y$ đều chia hết thì đếm.

Bị TLE chắc luôn

$X, Y$ có thể lên đến $10^9$. Khi đó phải lặp tới $10^9$ lần (duyệt tới $N/2$ thì cũng $5 \cdot 10^8$ lần) – vượt xa ngưỡng $(3 \div 5) \cdot 10^7$ hay cao lắm là $10^8$ của 1 giây. Mình thử với $X = Y = 10^9$ thì code C++ dưới đây chạy mất khoảng 8 giây. Cách này chỉ dùng để hiểu đề và làm code đối chiếu thôi nha.

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 x, y, res = 0;
    cin >> x >> y;
    for(long long i = 1; i <= min(x, y); ++i){
        if(x % i == 0 && y % i == 0){
            res++;
        }
    }
    cout << res;
    return 0;
}

x, y = map(int, input().split())
res = 0
for i in range(1, min(x, y) + 1):
    if x % i == 0 and y % i == 0:
        res += 1
print(res)

Không gian$O(1)$

Thời gian$O(\min(X, Y))$

Cách 2Duyệt ước theo cặp đến √min(X, Y) – O(√min(X, Y))

Chỉ có cách duyệt tới căn là ổn: với $N = 10^9$ thì số lần lặp chỉ hơn $3 \cdot 10^4$, thấp hơn ngưỡng rất nhiều, yên tâm không bị TLE. Ý tưởng duyệt tới căn: các ước của một số luôn đi theo cặp $(i, \frac{N}{i})$, trong đó số nhỏ $i \le \sqrt{N}$. Nên chỉ cần cho $i$ chạy tới khi $i \cdot i \le N$, mỗi lần gặp $i$ là ước thì ta có luôn ước "anh em" $\frac{N}{i}$.

Cách làm

Chọn số nhỏ hơn trong hai số (gọi là Min), duyệt tất cả ước của nó theo cặp $(i, temp = Min / i)$. Với mỗi ước tìm được, kiểm tra số còn lại (Max) có chia hết cho nó không, có thì tăng biến đáp án.

Tại sao chọn số nhỏ hơn? Thật ra chọn đại $X$ hay $Y$ cũng ra đúng, nhưng xét theo Min thì vòng lặp chạy ít hơn nhiều. Các bạn tưởng tượng $X = 10$, $Y = 10^9$: duyệt ước của $Y$ phải lặp hơn $3 \cdot 10^4$ lần, còn duyệt ước của $X$ thì chỉ 3 lần là xong ($i = 1, 2, 3$).

Các bạn nhập $X$, $Y$ vào khung dưới rồi bấm Tiếp để xem từng cặp ước của Min được xét (xanh: cũng là ước của Max ⇒ được đếm; đỏ: không phải ước của Max):

X Y

Ví dụ nhanh:

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 x, y, i, temp, Min, Max, res = 0;
    cin >> x >> y;
    Min = min(x, y);
    Max = max(x, y);
    for(i = 1; i * i <= Min; ++i){
        if(Min % i == 0){
            temp = Min / i;
            if(Max % i == 0){
                res++;
            }
            if(temp != i && Max % temp == 0){
                res++;
            }
        }
    }
    cout << res;
    return 0;
}

x, y = map(int, input().split())
Min, Max = min(x, y), max(x, y)
res = 0
i = 1
while i * i <= Min:
    if Min % i == 0:
        temp = Min // i
        if Max % i == 0:
            res += 1
        if temp != i and Max % temp == 0:
            res += 1
    i += 1
print(res)

Giải thích một số chỗ trong code:

1. Tất cả biến mình đều để kiểu long long (8 byte, kiểu số nguyên lớn nhất trong C/C++), dù dữ liệu bài này chưa chắc cần nhiều đến thế, nhưng để cho chắc, tránh mấy tình huống tràn số (ví dụ i * i).
2. Điều kiện vòng lặp là i * i <= Min chính là duyệt tới $\sqrt{Min}$ như phân tích ở trên.
3. Khi Min chia hết cho i (tức i là ước của Min), tính temp = Min / i là ước còn lại trong cặp. Sau đó kiểm tra cả 2 ước i và temp xem có là ước của Max luôn không. Với temp phải thêm điều kiện temp != i để đề phòng trường hợp như Min = 100, i = 10 thì temp = 100 / 10 = 10 trùng với i, nếu không chặn thì 10 bị đếm 2 lần.

Hai cái if chứ không phải if – else if

Mỗi lần ta xét cả 2 ước i và temp, chứ không phải chỉ 1 trong 2. Nhiều bạn quen tay thêm chữ else trước cái if thứ hai là sai nhé: khi i đã được đếm thì temp sẽ bị bỏ qua.

Khung chạy tay (để dễ theo dõi, giới hạn $\min(X, Y) \le 10^6$):

C++▶ Chạy tay từng dòng codeCách 2: duyệt ước của Min theo cặp (i, Min / i), đếm những ước mà Max cũng chia hết.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 long long x, y, i, temp, Min, Max, res = 0;

6 cin >> x >> y;

7 Min = min(x, y);

8 Max = max(x, y);

9 for(i = 1; i * i <= Min; ++i){

10 if(Min % i == 0){

11 temp = Min / i;

12 if(Max % i == 0){

13 res++;

14 }

15 if(temp != i && Max % temp == 0){

16 res++;

17 }

18 }

19 }

20 cout << res;

21 return 0;

22}

ChậmVừaNhanhRất nhanh

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

• Không gian: chỉ vài biến – $O(1)$.
• Thời gian: vòng lặp chạy tới $\sqrt{\min(X, Y)}$, tối đa khoảng $31\,623$ lần khi $\min(X, Y) = 10^9$ ⇒ $O(\sqrt{\min(X, Y)})$.

Không gian$O(1)$

Thời gian$O(\sqrt{\min(X, Y)})$

Mở rộng thêm

Một số là ước chung của $X$ và $Y$ khi và chỉ khi nó là ước của $\gcd(X, Y)$. Nên bài này cũng chính là "đếm số ước của $\gcd(X, Y)$" – lúc đó có thể dùng luôn cách phân tích thừa số nguyên tố (cách 4 đếm ước) trên $\gcd(X, Y)$. Với giới hạn $10^9$ thì cách duyệt tới căn ở trên là đủ nhanh rồi nha.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 300 bộ test ngẫu nhiên ($X, Y \le 2 \cdot 10^4$, có cả các cặp chia hết cho nhau), so với kết quả đếm ước của $\gcd(X, Y)$ – khớp hết, test của đề in ra 3. Với $X, Y$ cỡ $10^9$, Cách 2 C++ chạy khoảng 0.02 giây, Python khoảng 0.1 giây; còn Cách 1 C++ mất 5–8 giây (TLE như phân tích).

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 😇