Tìm 2 số
Đề bài
Cho 2 số nguyên dương $a$ và $b$. Bạn hãy tìm 2 số sau:
- Số thứ nhất là số lớn nhất $\le a$ mà chia hết cho $b$.
- Số thứ hai là số nhỏ nhất $\ge a$ mà chia hết cho $b$.
Input
- Dòng đầu tiên là số $T$ ($1 \le T \le 10^6$) là số lượng test case.
- $T$ dòng tiếp theo, mỗi dòng có 2 số $a$, $b$ cách nhau bởi 1 khoảng trắng ($1 \le a, b \le 10^{18}$).
Output: gồm $T$ dòng, mỗi dòng có 2 số cách nhau bởi 1 khoảng trắng.
Subtask
- 50% số test đầu tiên có $T \le 10$ và $a, b \le 10^6$.
- 50% số test còn lại không có giới hạn gì thêm.
2
17 5
717 68915 20
689 1378Lờ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ày chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesTóm lại đề bài cho bạn nào không hiểu: cho 2 số nguyên $a$, $b$. Hãy in ra màn hình 2 kết quả. Kết quả đầu tiên là giá trị lớn nhất thỏa mãn $\le a$ sao cho giá trị đó chia hết cho $b$. Kết quả tiếp theo là giá trị nhỏ nhất thỏa mãn $\ge a$ sao cho giá trị đó chia hết cho $b$. Thì đề bài đưa ra test ví dụ số to quá chắc cố tình để các bạn bị rối không nhìn thấy rõ, giờ mình đưa ra ví dụ nhỏ hơn như sau: $a = 17$, $b = 5$. Thì kết quả đầu tiên sẽ là 15, vì 15 là số lớn nhất $\le 17$ mà chia hết cho 5. Kết quả tiếp theo sẽ là 20, vì 20 là số nhỏ nhất $\ge 17$ mà chia hết cho 5.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
50%Cách 1: vét cạn bằng vòng lặp – O(T × B)
Một cách làm cơ bản nhất có thể nhìn ra đó là vét cạn (Brute Force).
Ta có thể thấy kết quả đầu tiên là giá trị lớn nhất thỏa $\le a$, thì nghĩa là xét từ $a$ giảm dần đều 1 đơn vị: $a$, $a - 1$, $a - 2$, $a - 3$, … rồi gặp giá trị đầu tiên thỏa chia hết cho $b$ thì đó là đáp án. Vì đang xét từ lớn về nhỏ nên giá trị đầu tiên thỏa nó đảm bảo là giá trị lớn nhất thỏa mãn.
Rồi kết quả tiếp theo là giá trị nhỏ nhất thỏa $\ge a$, thì nghĩa là xét từ $a$ tăng dần đều 1 đơn vị: $a$, $a + 1$, $a + 2$, $a + 3$, … rồi gặp giá trị đầu tiên thỏa chia hết cho $b$ thì đó là đáp án. Vì đang xét từ nhỏ đến lớn nên giá trị đầu tiên thỏa nó đảm bảo là giá trị nhỏ nhất thỏa mãn.
GetMin, GetMax để trả về giá trị tương ứng 2 kết quả cần xuất ra. Mình gọi kết quả đầu tiên là hàm GetMin (vì $\le a$, tức là đang đi từ lớn về nhỏ nên mình gọi là GetMin), kết quả tiếp theo là hàm GetMax (vì $\ge a$, tức là đang đi từ nhỏ đến lớn nên mình gọi là GetMax). Hay các bạn có thể thấy kết quả đầu tiên lúc nào cũng sẽ thỏa mãn $\le$ kết quả tiếp theo, vì thế kết quả đầu tiên là Min, kết quả tiếp theo là Max, cứ nhớ vậy cho dễ nha các bạn.Vậy nếu giải quyết bài này theo hướng dùng vòng lặp thì hướng giải quyết như mình đã mô tả ở trên, source code để các bạn tham khảo theo hướng dùng vòng lặp như sau:
Xem code vét cạn (50% điểm)
#include <bits/stdc++.h>
using namespace std;
long long GetMin(long long a, long long b){
while(a % b != 0){
a--;
}
return a;
}
long long GetMax(long long a, long long b){
while(a % b != 0){
a++;
}
return a;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long a, b, t;
cin >> t;
while(t--){
cin >> a >> b;
cout << GetMin(a, b) << ' ' << GetMax(a, b) << '\n';
}
return 0;
}import sys
def get_min(a, b):
while a % b != 0:
a -= 1
return a
def get_max(a, b):
while a % b != 0:
a += 1
return a
input_data = sys.stdin.read().strip().split()
t = int(input_data[0])
idx = 1
for _ in range(t):
a = int(input_data[idx]); b = int(input_data[idx+1])
idx += 2
print(get_min(a, b), get_max(a, b))Rất dễ để hiểu code này đúng không các bạn? Vòng lặp while sẽ cứ lặp liên tục nếu thấy giá trị $a$ không chia hết cho $b$ (tức là vòng lặp chỉ dừng khi giá trị $a$ chia hết cho $b$). Rồi bên trong vòng lặp while, nếu là hàm GetMin thì $a$ giảm dần 1 đơn vị, nếu là hàm GetMax thì $a$ tăng dần 1 đơn vị. Cứ thế sau quá trình lặp ta trả về giá trị $a$ thôi, sẽ là giá trị đầu tiên thỏa mãn chia hết cho $b$.
Đánh giá độ phức tạp thời gian của code trên:
- Giả sử ở hàm
GetMin, trong trường hợp xấu nhất, ví dụ như ngay từ đầu $a$ nhỏ hơn $b$ (ví dụ $a = b - 1$), thì rõ ràng sẽ không thể nào $a$ chia hết cho $b$, và cứ thế $a$ giảm lần lượt 1 đơn vị cho đến khi $a = 0$ thì khi đó mới chia hết cho $b$. Điều đó nghĩa là vòng lặp sẽ lặp gần hết $b$ lần. - Tương tự ở hàm
GetMax, trong trường hợp xấu nhất, ví dụ như ngay từ đầu $a$ nhỏ hơn $b$ (ví dụ $a = 1$), thì rõ ràng sẽ không thể nào $a$ chia hết cho $b$, và cứ thế $a$ tăng lần lượt 1 đơn vị cho đến khi $a = b$ thì khi đó mới chia hết cho $b$. Điều đó nghĩa là vòng lặp sẽ lặp gần hết $b$ lần.
Và ta có $T$ bộ test, nên tổng độ phức tạp của cách làm này là $O(T \times B)$. Thì chỉ lấy được subtask 1 với 50% đầu tiên khi $T$ tối đa là 10, $B$ tối đa là $10^6$, thì $T \times B = 10^7$ sẽ chạy được trong 1 giây. Còn với subtask 2 khi $T$ tối đa $10^6$ và $B$ tối đa $10^{18}$ thì $T \times B = 10^{24}$, thì phải chạy mất $10^{24} / 10^8 = 10^{16}$ giây = hơn 317 triệu năm chứ mấy 🤪
100%Cách 2: dùng phép chia lấy dư – O(1) mỗi test
Bây giờ ta nói về cách làm tối ưu. Thì ở đây sẽ rất đơn giản nếu bạn nào đã biết những phép tính modulo, cụ thể trong trường hợp này là 2 phép cộng trừ, ta có:
(a − b) % c = ((a % c) − (b % c)) % c
Thử kiểm chứng tính chính xác của 2 công thức trên với ví dụ $a = 17$, $b = 5$, $c = 4$. Thì $17 + 5 = 22$, $22 \% 4 = 2$. Thì nếu tách ra: $17 \% 4 = 1$, $5 \% 4 = 1$, rồi $1 + 1 = 2$, $2 \% 4 = 2$ ⇒ cũng y như lấy $22 \% 4 = 2$ các bạn thấy không? Cũng như $17 - 5 = 12$, $12 \% 4 = 0$. Thì nếu tách ra: $17 \% 4 = 1$, $5 \% 4 = 1$, $1 - 1 = 0$, $0 \% 4 = 0$ ⇒ cũng y như lấy $12 \% 4 = 0$ các bạn thấy không? Và các bạn có thể kiểm tra qua nhiều ví dụ khác nữa nhé, nhưng tóm lại đây là công thức chuẩn nha các bạn.
Hàm GetMin: số lớn nhất ≤ a chia hết cho b
Vậy vận dụng công thức này vào thế nào? Đầu tiên ở hàm GetMin, có phải ta cần tìm ra 1 giá trị đầu tiên thỏa $\le a$ sao cho giá trị đó chia hết cho $b$ đúng không? Thì nghĩa là ta sẽ hiểu giá trị cần tìm sẽ là $a - x$ sao cho $(a - x)$ chia hết cho $b$ với $x \ge 0$. Nghĩa là: (a - x) % b = 0. Lúc này khai triển ra tương đương là: ((a % b) - (x % b)) % b = 0.
Thì trong trường hợp bài này chỉ có 2 thông số $a$, $b$ nên giá trị $x$ chắc chắn phải phụ thuộc theo 2 thông số $a$, $b$ này. Ta có thể thấy nếu chọn $x = a$ luôn thì như thế ((a % b) - (a % b)) % b = 0 % b = 0 là luôn đúng. Mà nếu chọn $x = a$ thì lúc này $a - x$ luôn bằng 0, nghĩa là giá trị lớn nhất thỏa $\le a$ luôn là 0, mà nếu như thế ta thấy rõ là sai rồi, vì ngay với ví dụ đưa ra $a = 17$, $b = 5$ thì kết quả đầu tiên phải là 15, nhưng nếu theo cách này thì kết quả chỉ là 0. Vậy ta phải xem chọn lại giá trị $x$, cố gắng làm sao cho nó phụ thuộc theo cả 2 giá trị $a$, $b$.
Hãy nhìn lại biểu thức: ((a % b) - (x % b)) % b = 0. Ta có thể nhìn ra nếu chọn $x = a \% b$ thì lúc này biểu thức sẽ là: ((a % b) - ((a % b) % b)) % b = 0. Ở biểu thức (a % b) % b, ta thấy tính a % b xong giá trị thu được sẽ luôn đảm bảo $\lt b$, đây là nguyên tắc của phép toán chia lấy dư: phần dư luôn đảm bảo nhỏ hơn số chia. Nên nếu kết quả thu được chắc chắn đã nhỏ hơn $b$ thì việc tiếp tục lấy giá trị đó % b sẽ vẫn là giá trị đó. Bởi 1 số nhỏ chia lấy dư cho 1 số lớn thì kết quả vẫn là số nhỏ đó: số nhỏ chia cho số lớn thì phần nguyên luôn là 0, thì phần dư chính là toàn bộ còn lại. Vậy nên (a % b) % b ⇔ a % b.
Nên khi chọn $x = a \% b$, giờ đây biểu thức sẽ là ((a % b) - (a % b)) % b = 0 % b = 0, điều này luôn đúng vì giá trị 0 chia cho bất kỳ giá trị nào đều sẽ bằng 0. Vậy kết quả đầu tiên sẽ là $a - x$ với $x$ giờ đây là $a \% b$, nên kết quả sẽ là: a − (a % b). Thử nhẩm với $a = 17$, $b = 5$ thì kết quả đầu tiên là: $17 - (17 \% 5) = 17 - 2 = 15$. Đúng hen các bạn.
Vậy nên ta có hàm GetMin theo công thức sử dụng Mod như sau:
long long GetMin(long long a, long long b){
return a - (a % b);
}Hàm GetMax: số nhỏ nhất ≥ a chia hết cho b
Tiếp tục thử suy luận xem hàm GetMax sẽ có công thức thế nào? Có phải ta cần tìm ra giá trị đầu tiên thỏa $\ge a$ sao cho giá trị đó chia hết cho $b$. Nghĩa là kết quả sẽ là $(a + x)$ với $x \ge 0$ sao cho $(a + x)$ chia hết cho $b$. Tức là: (a + x) % b = 0 ⇔ ((a % b) + (x % b)) % b = 0. Vậy phải chọn $x$ bằng bao nhiêu?
Ta có thể thấy nếu muốn vế bên trái cho kết quả bằng 0 để 0 % b = 0 là đúng, thì $x$ nên chọn là $-(a \% b)$. Lúc này ((a % b) + (-(a % b))) % b = 0 % b = 0 luôn đúng (phép $+$ $-$ đứng cạnh nhau thì triệt tiêu dấu $+$, giữ lại dấu $-$, đây là quy tắc toán học căn bản). Vậy khi chọn $x = -(a \% b)$ thì giờ đây kết quả sẽ là $a + x$, tức là $a + (-(a \% b))$ ⇔ $a - (a \% b)$.
GetMax phải trả ra 20 mà?Và chỗ này ta hiểu khi chọn $x = -(a \% b)$ thì $a + x$ ⇔ $a - (a \% b)$ đã không đúng ở chỗ: giá trị $a \% b$ thu được nằm trong đoạn từ $0$ đến $b - 1$. Nếu kết quả là 0 thì $a - 0$ vẫn là $a$, vẫn thỏa; nhưng chỉ cần kết quả khác 0 thì $a$ trừ kết quả đó sẽ ra giá trị nhỏ hơn $a$, mà như thế lại sai với yêu cầu đề bài ở chỗ này là phải tìm ra giá trị $\ge a$.
Vậy nên nếu muốn kết quả vừa chia hết cho $b$ nhưng đảm bảo $\ge a$ thì ta sẽ cộng thêm giá trị $b$ vào $x$, tức là chọn $x = -(a \% b) + b$. Lúc này $a + x$ ⇔ $a - (a \% b) + b$. Tại vì giá trị $a - (a \% b)$ đã chia hết cho $b$, nếu không thỏa mãn $\ge a$ thì giá trị nhỏ nhất tiếp theo có thể cộng thêm vào sao cho vẫn chia hết cho $b$ chính là giá trị $b$. Vì thế đáp án sẽ là: a + b − (a % b) (còn nếu $a \% b = 0$ thì $a$ đã chia hết cho $b$, trả về luôn $a$).
Kiểm tra với $a = 17$, $b = 5$: GetMin $= 17 - 2 = 15$, GetMax $= 17 + 5 - 2 = 20$ ✔
Em nhập $a$, $b$ (nhỏ thôi) rồi bấm Tiếp để xem 2 công thức bằng hình: mỗi ô là 1 đơn vị, gom thành từng nhóm $b$ ô:
Vậy nên ta có hàm GetMax theo công thức sử dụng Mod như sau:
long long GetMax(long long a, long long b){
long long m = a % b;
if(m == 0){
return a;
}
return a + b - m;
}Vậy ta có chương trình hoàn chỉnh như sau:
#include <bits/stdc++.h>
using namespace std;
long long GetMin(long long a, long long b){
return a - (a % b);
}
long long GetMax(long long a, long long b){
long long m = a % b;
if(m == 0){
return a;
}
return a + b - m;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long t, a, b;
cin >> t;
while(t--){
cin >> a >> b;
cout << GetMin(a, b) << ' ' << GetMax(a, b) << '\n';
}
return 0;
}import sys
def get_min(a, b):
return a - (a % b)
def get_max(a, b):
m = a % b
if m == 0:
return a
return a + b - m
data = sys.stdin.buffer.read().split()
t = int(data[0])
out_lines = []
idx = 1
for _ in range(t):
a = int(data[idx]); b = int(data[idx + 1])
idx += 2
out_lines.append(f"{get_min(a, b)} {get_max(a, b)}")
sys.stdout.write("\n".join(out_lines))Độ phức tạp: mỗi test chỉ tốn vài phép tính nên tổng là $O(T)$. Mình chạy thử với $T = 10^6$ cặp số ngẫu nhiên tới $10^{18}$: bản C++ khoảng 0.3 giây, bản Python khoảng 1.3 giây. Các bạn yên tâm là $a + b \le 2 \cdot 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 số nhé.
Viết gọn trong 1 dòng
Do mình làm chia hàm ra cho các bạn dễ thấy, chứ nếu muốn code nhanh gọn có thể chỉ cần 1 dòng xử lý duy nhất là được nha các bạn:
Xem code viết gọn 1 dòng
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long t, a, b;
cin >> t;
while(t--){
cin >> a >> b;
cout << a - (a % b) << ' '
<< (a % b == 0 ? a : a + b - (a % b)) << '\n';
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
t = int(data[0])
out_lines = []
idx = 1
for _ in range(t):
a = int(data[idx]); b = int(data[idx + 1])
idx += 2
left = a - (a % b)
right = a if a % b == 0 else a + b - (a % b)
out_lines.append(f"{left} {right}")
sys.stdout.write("\n".join(out_lines))
Nhận xét
Đăng nhận xét