Tích lớn nhất ver 4

Nguồn: CLUE OJ – Chương 45: Đồng dư modulo Độ khó: Trung bình Tràn số Nhân lấy dư

Đề bài

Cho ba số nguyên $a, b, c$ và một số nguyên dương $M$.

Yêu cầu: hãy tìm tích lớn nhất được tạo bởi hai trong ba số $a, b, c$. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư khi chia cho $M$.

Dữ liệu: vào từ tệp văn bản BAI3.INP gồm bốn số nguyên $a, b, c, M$. Các số cách nhau một dấu cách.

Kết quả: ghi ra tệp văn bản BAI3.OUT một số nguyên duy nhất là kết quả bài toán.

Giới hạn:

• Có $70\%$ số test tương ứng với số điểm có $|a|, |b|, |c| \le 10^9$, $1 \le M \le 10^9$;
• $30\%$ số test còn lại có $|a|, |b|, |c| \le 10^{18}$, $1 \le M \le 10^{18}$.

Ví dụ 1 – input

3 2 5 4

Ví dụ 1 – output

3

Ví dụ 2 – input

2 -3 -2 100

Ví dụ 2 – output

6

Giải thích: ví dụ 1 có tích lớn nhất là $3 \times 5 = 15$, $15$ chia $4$ dư $3$. Ví dụ 2 có tích lớn nhất là $(-2) \times (-3) = 6$, $6$ chia $100$ dư $6$.

Lưu ý nộp bài: trên CLUE OJ bài này đọc/ghi qua tệp BAI3.INP / BAI3.OUT. Trong code mình dùng if (fopen("BAI3.INP", "r")) { freopen(...); freopen(...); }: có tệp thì đọc tệp, không có thì tự đọc bàn phím.

Lời mở đầu

Đề nghe rất dễ: lấy max của ba tích rồi chia lấy dư. Cái bẫy nằm ở con số $10^{18}$: tích hai số cỡ $10^{18}$ lên tới $10^{36}$, vượt xa long long (tối đa khoảng $9{,}2 \cdot 10^{18}$). Bài này dạy ta hai kỹ năng rất hay gặp trong chương đồng dư: chọn đúng cặp mà không cần tính tích, và nhân lấy dư hai số lớn mà không bị trà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

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

Bộ test20 test, 2 mứcÝ tưởngcặp nào, nhân thế nàoCách 1long longCách 2__int128Cách 3nhân Ấn ĐộTổng kếtkết quả chạy thật

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, chia đúng 2 mức như đề:

Test	$a, b, c$	$M$	Có số âm?
1 – 14	$< 10^9$	$21\,325\,515$ … $903\,475\,967$	không
15 – 20	$\approx 2{,}8 \cdot 10^{16}$ … $9{,}6 \cdot 10^{17}$	$2{,}8 \cdot 10^{17}$ … $9{,}7 \cdot 10^{17}$	không

• Test 1–14 ứng với $70\%$ (số $< 10^9$), test 15–20 ứng với $30\%$ (số tới gần $10^{18}$).
• Bộ test chính thức không có số âm (chỉ ví dụ 2 trong đề có). Dù vậy lời giải của mình vẫn xử lý đúng số âm như đề cho phép.

Subtask	Điều kiện	Các test	Cách ăn được
1 (70%)	$|a|,|b|,|c|, M \le 10^9$	1 – 14	Cách 1, 2, 3
2 (30%)	tới $10^{18}$	15 – 20	Cách 2, 3

Ý tưởngChọn cặp theo dấu, rồi nhân lấy dư không tràn

1) Cặp nào cho tích lớn nhất? Sắp xếp $v_0 \le v_1 \le v_2$. Tích lớn nhất chỉ có thể là $v_1 v_2$ (hai số lớn nhất) hoặc $v_0 v_1$ (hai số nhỏ nhất – khi cả hai âm thì tích dương lớn). So sánh:

Nhận xét

$$v_1 v_2 - v_0 v_1 = v_1 (v_2 - v_0) \quad\Rightarrow\quad v_1 v_2 \ge v_0 v_1 \iff v_1 \ge 0$$

Vậy chỉ cần nhìn dấu của số ở giữa: $v_1 \ge 0$ thì lấy $v_1 v_2$, ngược lại lấy $v_0 v_1$. Không cần tính tích nào cả! Thêm nữa, trong 3 số luôn có 2 số cùng dấu, nên tích lớn nhất luôn $\ge 0$ – ta chỉ cần nhân hai trị tuyệt đối.

2) Nhân lấy dư hai số tới $10^{18}$. Dùng tính chất đồng dư $(x \cdot y) \bmod M = \big((x \bmod M)(y \bmod M)\big) \bmod M$ vẫn chưa đủ, vì $x \bmod M$ vẫn cỡ $10^{18}$. Ta có 2 hướng: dùng kiểu __int128 (chứa tới $1{,}7 \cdot 10^{38}$), hoặc nhân Ấn Độ: viết $y$ ở hệ nhị phân, $x \cdot y = \sum x \cdot 2^i$ với các bit $i$ bằng 1, mỗi bước chỉ cộng hai số $< M$ nên không bao giờ vượt $2M \le 2 \cdot 10^{18}$.

Nhân Ấn Độ

$$\text{res} \mathrel{+}= x \text{ (nếu bit cuối của } y = 1), \qquad x \leftarrow 2x \bmod M, \qquad y \leftarrow \lfloor y/2 \rfloor$$

Em nhập 4 số rồi bấm Tiếp để xem cả hai bước:

a, b, c, M =

Ví dụ nhanh:

Cách 1Tính thẳng 3 tích bằng long long

Làm đúng như đề: tính $ab$, $bc$, $ac$ bằng long long, lấy max rồi chia lấy dư cho $M$.

C++▶ Chạy tay từng dòng codeCách 1: tính 3 tích bằng long long, lấy max rồi % m.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Khi $|a|, |b|, |c| \le 10^9$ thì mỗi tích $\le 10^{18} < 9{,}2 \cdot 10^{18}$: vừa long long, đúng hết.
• Khi các số cỡ $10^{17}$–$10^{18}$, tích lên tới $10^{35}$: phép nhân bị tràn số (C++ chỉ giữ lại 64 bit cuối), kết quả là một số "rác", có thể âm. Em chọn dữ liệu mẫu "Số 10^18" ở khung chạy tay để thấy.
• Bản Python không bị tràn vì số nguyên Python tự mở rộng, nên cách 1 viết bằng Python vẫn đúng hết.

Không gian$O(1)$

Thời gian$O(1)$

Kết quả chạy thật: bản C++ đúng 14/20 test (Subtask 1: 14/14, Subtask 2: 0/6) – cả 6 test lớn đều sai kết quả do tràn số. Bản Python đúng 20/20.

Cách 2Dùng __int128 – full điểm

GCC hỗ trợ kiểu số nguyên 128 bit __int128, chứa được tới khoảng $1{,}7 \cdot 10^{38}$ – thoải mái cho tích hai số $10^{18}$. Ta ép kiểu trước khi nhân: (__int128)a * b. Lưu ý cin/cout không đọc/in trực tiếp __int128, nên ta đọc bằng long long, và chỉ in ra số dư (đã nhỏ hơn $M$, vừa long long).

C++▶ Chạy tay từng dòng codeCách 2: ép kiểu __int128 trước khi nhân nên không tràn.

Dữ liệu vào (stdin) – sửa thoải mái910234909537395574 106956154608311363 504076968027338995 598434990378475204

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Phải ép trước khi nhân: (__int128)(a * b) là sai, vì a * b đã tràn ở kiểu long long rồi mới ép.
• Vì trong 3 số luôn có 2 số cùng dấu, best luôn $\ge 0$ nên best % m không âm.
• Bản Python: số nguyên Python tự mở rộng, viết y như cách 1.

Không gian$O(1)$

Thời gian$O(1)$

Kết quả chạy thật: bản C++ đúng 20/20 test, bản Python đúng 20/20 test.

Cách 3Chọn cặp theo dấu + nhân Ấn Độ – không cần __int128

__int128 không phải trình biên dịch nào cũng có (ví dụ một số máy chấm Pascal, hay C++ của Visual Studio). Cách 3 chỉ dùng long long: sắp xếp, chọn cặp theo dấu của số ở giữa như phần Ý tưởng, rồi nhân lấy dư bằng nhân Ấn Độ.

C++▶ Chạy tay từng dòng codeCách 3: sort, chọn cặp theo dấu v[1], rồi mulmod bằng cộng dồn (không bao giờ vượt 2m).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Trong mulmod, res và x luôn $< m \le 10^{18}$ nên res + x và x + x đều $< 2 \cdot 10^{18}$ – không tràn long long.
• Vòng lặp chạy theo số bit của $y$: tối đa khoảng 60 lần.
• llabs lấy trị tuyệt đối cho long long. Lấy trị tuyệt đối là an toàn vì tích lớn nhất luôn $\ge 0$.

Không gian$O(1)$

Thời gian$O(\log y) \approx 60$ phép tính

Kết quả chạy thật: bản C++ đúng 20/20 test, bản Python đúng 20/20 test.

Tổng kếtKết quả chạy thật trên bộ test

Mình chấm cả 3 cách (C++ và Python) trên toàn bộ 20 test với giới hạn 1 giây, đo thời gian CPU:

Lời giải	Subtask 1 test 1–14	Subtask 2 test 15–20	Tổng	CPU lớn nhất
Cách 1 – C++	14/14	0/6	14/20	0,006s
Cách 1 – Python	14/14	6/6	20/20	0,056s
Cách 2 – C++	14/14	6/6	20/20	0,005s
Cách 2 – Python	14/14	6/6	20/20	0,029s
Cách 3 – C++	14/14	6/6	20/20	0,005s
Cách 3 – Python	14/14	6/6	20/20	0,029s

Ghi chú của mình: cách 1 bằng C++ sai đúng 6 test lớn vì tràn số (không phải quá thời gian). Cách 2 gọn nhất nếu được dùng __int128; cách 3 là kỹ thuật "nhân Ấn Độ" dùng được ở mọi ngôn ngữ, và nhận xét "nhìn dấu của số ở giữa" giúp chọn cặp mà không cần nhân. Python không lo tràn số nên cả 3 cách đều đúng.

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 😇