Bánh pía kẹo dừa (Đề tự luyện HSG Tin 12 – Bài 3)
Đề bài
Bánh pía kẹo dừa. Bánh pía giá $a$, kẹo dừa giá $b$ (nghìn đồng/hộp). Thầy Sơn muốn tiêu vừa đúng $S$ nghìn: mua $x$ hộp bánh pía và $y$ hộp kẹo dừa với $x, y \ge 0$ nguyên và $ax + by = S$. Hỏi có bao nhiêu cách mua, và trong các cách đó $|x - y|$ nhỏ nhất bằng bao nhiêu? Có $T$ câu hỏi.
Dữ liệu vào: dòng đầu $T$ ($1 \le T \le 10^5$); mỗi dòng sau gồm $a, b, S$ ($1 \le a, b \le 10^9$, $1 \le S \le 10^{18}$).
Kết quả: mỗi câu hỏi in số cách mua và $|x - y|$ nhỏ nhất; không có cách nào thì in 0 -1.
- Subtask 1 (25%): $T \le 10$ và $S \le 10^6$.
- Subtask 2 (25%): $a, b \le 1000$.
- Subtask 3 (50%): không có ràng buộc gì thêm.
4
75 15 405
20 17 632
60 70 105
20 35 856 3
2 2
0 -1
0 -1Câu 1: sáu cách $(0, 27), (1, 22), (2, 17), (3, 12), (4, 7), (5, 2)$, chênh lệch nhỏ nhất $3$. Câu 2: hai cách $(1, 36)$ và $(18, 16)$, chênh lệch nhỏ nhất $2$. Câu 3, 4: không có cách nào.
Bạ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é. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Bánh pía kẹo dừaLời mở đầu
Đây là bài toán phương trình Diophantine bậc nhất hai ẩn $ax + by = S$ (tìm nghiệm nguyên) – thêm điều kiện $x, y \ge 0$, đếm số nghiệm và tìm nghiệm "cân đối" nhất. Với $S$ tới $10^{18}$ và $10^5$ câu hỏi, mình cần công thức gần như $O(1)$ cho mỗi câu. Trước hết là ba nhận xét nền tảng.
Nhận xét 1 – khi nào có nghiệm. Gọi $g = \gcd(a, b)$. Vế trái $ax + by$ luôn chia hết cho $g$, nên nếu $S$ không chia hết cho $g$ thì chắc chắn vô nghiệm (câu 3 của ví dụ: $\gcd(60, 70) = 10$ còn $105$ không chia hết cho $10$). Ngược lại, chia cả phương trình cho $g$: đặt $a' = a/g$, $b' = b/g$, $S' = S/g$, ta được $a'x + b'y = S'$ với $\gcd(a', b') = 1$.
Nhận xét 2 – các nghiệm cách đều nhau. Nếu $(x, y)$ là một nghiệm thì $(x + b', y - a')$ cũng là nghiệm (tiền bánh pía tăng $a \cdot b' = \text{lcm}(a, b)$, tiền kẹo dừa giảm đúng bấy nhiêu). Ngược lại, mọi nghiệm đều có dạng đó: từ $a'x_1 + b'y_1 = a'x_2 + b'y_2$ suy ra $a'(x_1 - x_2) = b'(y_2 - y_1)$, mà $\gcd(a', b') = 1$ nên $b'$ chia hết $x_1 - x_2$.
Nhận xét 3 – đếm và cân đối. Gọi $x_0$ là nghiệm $x$ nhỏ nhất ($0 \le x_0 < b'$) và $y_0 = (S' - a'x_0)/b'$ là $y$ tương ứng (lớn nhất). Nếu $y_0 < 0$ thì vô nghiệm. Ngược lại các nghiệm là
$$(x_0 + k b',\ y_0 - k a'), \quad k = 0, 1, \ldots, K, \qquad K = \left\lfloor \frac{y_0}{a'} \right\rfloor,$$
tức có $K + 1$ cách mua. Độ chênh lệch $x - y = (x_0 - y_0) + k(a' + b')$ tăng đều theo $k$ (bước $a' + b'$), nên $|x - y|$ nhỏ nhất đạt tại $k$ làm $x - y$ "đổi dấu": $k^* = \left\lfloor \frac{y_0 - x_0}{a' + b'} \right\rfloor$ hoặc $k^* + 1$ – nhớ kẹp vào đoạn $[0, K]$.
Hình 1. Các nghiệm của câu 1 xếp thành cấp số cộng; $x - y$ tăng đều nên chỉ cần xét hai nghiệm quanh chỗ đổi dấu.
Phần còn lại chỉ là: tìm $x_0$ thế nào cho nhanh. Ba cách dưới đây khác nhau đúng ở chỗ đó.
Cách 1Thử mọi số hộp bánh pía – O(S/a) mỗi câu · 25%
Thử $x = 0, 1, 2, \ldots$ chừng nào $ax \le S$; nếu $S - ax$ chia hết cho $b$ thì được một cách mua với $y = (S - ax)/b$, cập nhật số cách và $|x - y|$ nhỏ nhất. Với $S \le 10^6$ và $T \le 10$ thì nhiều nhất $10^7$ phép thử.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int T; cin >> T;
while (T--) {
ll a, b, S; cin >> a >> b >> S;
ll cnt = 0, best = -1;
for (ll x = 0; a * x <= S; x++)
if ((S - a * x) % b == 0) {
ll y = (S - a * x) / b; cnt++;
if (best < 0 || llabs(x - y) < best) best = llabs(x - y);
}
cout << cnt << " " << best << "\n";
}
}import sys
def main():
data = sys.stdin.buffer.read().split()
T = int(data[0])
out = []
for i in range(T):
a = int(data[1 + 3 * i]); b = int(data[2 + 3 * i]); S = int(data[3 + 3 * i])
cnt = 0; best = -1
x = 0
while a * x <= S: # thu moi so hop banh pia x
r = S - a * x
if r % b == 0: # phan con lai mua tron hop keo dua
y = r // b
cnt += 1
if best < 0 or abs(x - y) < best:
best = abs(x - y)
x += 1
out.append("%d %d" % (cnt, best))
sys.stdout.write("\n".join(out) + "\n")
main()Cách 2Tìm nghiệm nhỏ nhất bằng cách thử x < b – O(b) mỗi câu · 50%
Điều kiện "$S - ax$ chia hết cho $b$" chỉ phụ thuộc vào $x \bmod b$ (vì $a(x + b) \equiv ax \pmod b$). Vậy nếu có nghiệm thì có nghiệm với $x < b$; ta thử $x = 0, 1, \ldots, b - 1$ và dừng ở giá trị đầu tiên thỏa – đó chính là $x_0$ nhỏ nhất. Không tìm thấy thì vô nghiệm. Có $x_0$ rồi thì áp dụng Nhận xét 3: $y_0 = (S - a x_0)/b$, $K = \lfloor y_0 / a' \rfloor$, rồi tìm $|x - y|$ nhỏ nhất quanh $k^*$.
/ làm tròn về 0 (-7 / 2 = -3), không phải làm tròn xuống ($\lfloor -3{,}5 \rfloor = -4$). Ở bài này ta xét cả $k^*$ và $k^* + 1$ rồi kẹp vào $[0, K]$ nên nhầm một chút cũng chưa chết, nhưng hãy tập thói quen viết hàm chia làm tròn xuống đúng nghĩa. Python thì // đã làm tròn xuống sẵn.Với $a, b \le 1000$: mỗi câu tốn tối đa $1000$ phép thử, $10^5$ câu là $10^8$ – vừa đủ nhanh.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
ll a, b, S;
cin >> a >> b >> S;
ll x = -1;
for (ll t = 0; t < b && a * t <= S; t++) // x va x + b cho cung so du khi chia b
if ((S - a * t) % b == 0) { x = t; break; }
if (x < 0) { cout << "0 -1\n"; continue; }
ll g = __gcd(a, b), a1 = a / g, b1 = b / g;
ll y = (S - a * x) / b; // x nho nhat, y lon nhat
ll K = y / a1; // nghiem thu k: (x + k*b1, y - k*a1)
ll d = x - y, s = a1 + b1;
ll best = LLONG_MAX;
ll k0 = (-d) / s - (((-d) % s != 0) && (-d < 0)); // lam tron xuong
for (ll k = k0; k <= k0 + 1; k++) {
ll kk = min(max(k, 0LL), K);
best = min(best, llabs(d + kk * s));
}
cout << K + 1 << " " << best << "\n";
}
return 0;
}import sys
from math import gcd
def main():
data = sys.stdin.buffer.read().split()
T = int(data[0])
out = []
for i in range(T):
a = int(data[1 + 3 * i]); b = int(data[2 + 3 * i]); S = int(data[3 + 3 * i])
x = -1
t = 0
while t < b and a * t <= S: # x va x + b cho cung so du khi chia b
if (S - a * t) % b == 0:
x = t; break
t += 1
if x < 0:
out.append("0 -1"); continue
g = gcd(a, b); a1 = a // g; b1 = b // g
y = (S - a * x) // b # x nho nhat, y lon nhat
K = y // a1 # nghiem thu k: (x + k*b1, y - k*a1)
d = x - y; s = a1 + b1
k0 = (-d) // s
best = -1
for k in (k0, k0 + 1):
kk = 0 if k < 0 else (K if k > K else k)
v = abs(d + kk * s)
if best < 0 or v < best:
best = v
out.append("%d %d" % (K + 1, best))
sys.stdout.write("\n".join(out) + "\n")
main()Cách 3Euclid mở rộng – O(log) mỗi câu · 100%
Khi $b$ tới $10^9$ thì không thử nổi. Ta cần tính thẳng $x_0$ từ phương trình đồng dư $a'x \equiv S' \pmod{b'}$.
Thuật toán Euclid mở rộng tìm được $g = \gcd(a, b)$ cùng hai số nguyên $p, q$ với $ap + bq = g$. Ý tưởng đệ quy: $\gcd(a, b) = \gcd(b, a \bmod b)$; nếu đã có $p_1, q_1$ với $b p_1 + (a \bmod b) q_1 = g$, thay $a \bmod b = a - \lfloor a/b \rfloor b$ ta được
$$a \cdot q_1 + b \cdot \left(p_1 - \left\lfloor \frac{a}{b} \right\rfloor q_1\right) = g,$$
tức $p = q_1$, $q = p_1 - \lfloor a/b \rfloor q_1$. Điểm dừng $b = 0$: $a \cdot 1 + 0 \cdot 0 = a$.
Chia hai vế $ap + bq = g$ cho $g$: $a'p + b'q = 1$, nghĩa là $a'p \equiv 1 \pmod{b'}$ – $p$ là nghịch đảo của $a'$ theo modulo $b'$. Nhân hai vế đồng dư $a'x \equiv S'$ với $p$:
$$x \equiv p \cdot S' \pmod{b'} \quad\Rightarrow\quad x_0 = \big((p \bmod b') \cdot (S' \bmod b')\big) \bmod b'.$$
- $p$ có thể âm (ví dụ $\gcd(3, 5)$: $3 \cdot 2 + 5 \cdot (-1) = 1$ nhưng với $(5, 3)$ ta được $5 \cdot (-1) + 3 \cdot 2 = 1$). Trong C++,
p % b1vẫn âm nếu $p$ âm – phải cộng thêmb1. - Tràn số: $|p| < b' \le 10^9$ nhưng $S'$ tới $10^{18}$, nên
p * S'trànlong long. Phải lấyS' % b'trước: hai thừa số đều dưới $10^9$, tích dưới $10^{18}$ – an toàn.
Phần còn lại giống Cách 2. Các bạn nhập thử $a, b, S$ để xem bảng Euclid mở rộng và cách tìm đáp án:
Code hoàn chỉnh:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Tra ve g = gcd(a, b) va tim p, q voi a*p + b*q = g (Euclid mo rong)
ll exgcd(ll a, ll b, ll &p, ll &q) {
if (b == 0) { p = 1; q = 0; return a; }
ll p1, q1;
ll g = exgcd(b, a % b, p1, q1);
p = q1; q = p1 - (a / b) * q1;
return g;
}
ll floorDiv(ll a, ll b) { // lam tron xuong that su (b > 0)
return a / b - ((a % b != 0) && (a < 0));
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
ll a, b, S;
cin >> a >> b >> S;
ll p, q;
ll g = exgcd(a, b, p, q);
if (S % g != 0) { cout << "0 -1\n"; continue; }
ll a1 = a / g, b1 = b / g, s1 = S / g; // a1*x + b1*y = s1, gcd(a1, b1) = 1
// a1*p = 1 (mod b1) => x = p*s1 (mod b1) la x nho nhat
p %= b1; if (p < 0) p += b1;
ll x = (p * (s1 % b1)) % b1; // ca hai thua so < b1 <= 1e9: khong tran
if (a1 * x > s1) { cout << "0 -1\n"; continue; }
ll y = (s1 - a1 * x) / b1; // y lon nhat
ll K = y / a1; // nghiem thu k: (x + k*b1, y - k*a1), k = 0..K
ll d = x - y, s = a1 + b1; // chenh lech x - y tang them s moi buoc
ll best = LLONG_MAX;
ll k0 = floorDiv(-d, s); // d + k*s doi dau giua k0 va k0 + 1
for (ll k = k0; k <= k0 + 1; k++) {
ll kk = min(max(k, 0LL), K);
best = min(best, llabs(d + kk * s));
}
cout << K + 1 << " " << best << "\n";
}
return 0;
}import sys
def exgcd(a, b):
# tra ve (g, p, q) voi a*p + b*q = g = gcd(a, b) (Euclid mo rong, viet lap)
p0, q0, p1, q1 = 1, 0, 0, 1
while b:
t = a // b
a, b = b, a - t * b
p0, p1 = p1, p0 - t * p1
q0, q1 = q1, q0 - t * q1
return a, p0, q0
def main():
data = sys.stdin.buffer.read().split()
T = int(data[0])
out = []
pos = 1
for _ in range(T):
a = int(data[pos]); b = int(data[pos + 1]); S = int(data[pos + 2]); pos += 3
g, p, q = exgcd(a, b)
if S % g:
out.append("0 -1"); continue
a1 = a // g; b1 = b // g; s1 = S // g # a1*x + b1*y = s1, gcd(a1, b1) = 1
x = (p % b1) * (s1 % b1) % b1 # x nho nhat
if a1 * x > s1:
out.append("0 -1"); continue
y = (s1 - a1 * x) // b1 # y lon nhat
K = y // a1 # nghiem thu k: (x + k*b1, y - k*a1), k = 0..K
d = x - y; s = a1 + b1 # chenh lech x - y tang them s moi buoc
k0 = (-d) // s # // cua Python lam tron xuong
best = -1
for k in (k0, k0 + 1):
kk = 0 if k < 0 else (K if k > K else k)
v = abs(d + kk * s)
if best < 0 or v < best:
best = v
out.append("%d %d" % (K + 1, best))
sys.stdout.write("\n".join(out) + "\n")
main()Bộ test chấm "bắt" những lỗi nào?
Bộ test có 29 test: 10 test subtask 1 ($T \le 10$, $S \le 10^6$), 9 test subtask 2 ($a, b \le 1000$, $T$ từ $6 \cdot 10^4$ tới $10^5$, $S$ tới $10^{18}$), 10 test subtask 3 ($T$ từ $6 \cdot 10^4$ tới $10^5$). Các câu hỏi được sinh có chủ đích: chắc chắn có nghiệm, có rất nhiều nghiệm với $x \approx y$ ở giữa, chia hết cho $\gcd$ nhưng vô nghiệm, không chia hết cho $\gcd$, $a = b$, $a = 1$ hoặc $b = 1$, $S$ nhỏ hơn cả hai giá, $S$ là bội của $\text{lcm}(a, b)$, số cách mua tới gần $10^{18}$.
| Cách làm | Sub 1 (25%) | Sub 2 (25%) | Sub 3 (50%) | Điểm |
|---|---|---|---|---|
| Cách 1 – thử mọi x | Đúng | TLE | TLE | 25 |
| Cách 2 – tìm x₀ trong [0, b) | Đúng | Đúng | TLE | 50 |
| Cách 3 – Euclid mở rộng | Đúng | Đúng | Đúng | 100 |
Sai 1 – quên đưa p âm về $[0, b')$ | 2/10 test | 0/9 test | 0/10 test | 5 |
Sai 2 – nhân p * S' trước khi lấy dư (tràn số) | Đúng | 1/9 test | 0/10 test | ≈ 28 |
| Sai 3 – quên kiểm tra $S$ chia hết cho $g$ | 7/10 test | 0/9 test | 1/10 test | 22,5 |
| Sai 4 – chỉ xét hai cách ở hai đầu ($x$ nhỏ nhất / lớn nhất) | 3/10 test | 0/9 test | 0/10 test | 7,5 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test subtask 1 và chạy quá 3 giây ở mọi test còn lại; Cách 2 đúng hết hai subtask đầu (test lâu nhất khoảng 0,1 giây) và quá 3 giây ở cả 10 test subtask 3; Cách 3 đúng 29/29 test, test lâu nhất khoảng 0,05 giây. Bộ test "khó tính" với các lỗi chi tiết: mỗi test lớn có hàng chục nghìn câu hỏi nên chỉ cần sai một câu là mất cả test – quên chuẩn hóa $p$ âm, quên kiểm tra $\gcd$ hay chỉ xét hai đầu mút đều gần như mất trắng; lỗi tràn số chỉ sống được ở subtask 1 vì ở đó $S$ nhỏ.
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 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét