Tính giá trị
Đề bài
Cho số nguyên dương $N$. Hãy tính và đưa ra $S$:
Input: một dòng duy nhất ghi số $N$ ($N \le 10^9$).
Output: một số nguyên duy nhất là số dư của $S$ trong phép chia cho $(10^6 + 7)$.
Ràng buộc
- Có 60% số test tương ứng với $N \le 10^3$.
- Có 30% số test khác tương ứng với $N \le 10^6$.
- Có 10% số test còn lại tương ứng với $N \le 10^9$.
320Lờ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 CodeforcesThì có thể nói rằng bài này là bài cho điểm, tức là nó là dễ nhất của đề thi. Nói là vậy nhưng nếu bạn nào không biết những công thức toán học thì sẽ không thể giải trọn vẹn được bài này đâu, tức là không ăn được trọn 100% điểm. Cụ thể những công thức toán học đó là gì? Thì chi tiết dưới đây mình sẽ phân tích cho các bạn thấy rõ.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
SaiCách 1: vòng lặp cơ bản – cái bẫy tràn số
Thì với đề bài tính $S = 1 \times 2 + 2 \times 3$ $+ 3 \times 4 + \ldots + N \times (N+1)$, đây có thể xem là bài ở mức độ nhập môn lập trình với một người mới bắt đầu học lập trình đến phần kiến thức vòng lặp. Thì cách giải quyết quá đơn giản: cho vòng lặp for $i$ chạy từ 1 đến $N$, với mỗi giá trị $i$ đi tính tích của $i$ với $i + 1$ rồi lấy kết quả đó cộng vào biến tổng $S$. Sau cùng khi vòng lặp chạy đủ $N$ lần xong thì in ra biến tổng $S$ đó chính là kết quả bài toán. Và theo như đề yêu cầu thì kết quả đó sẽ chia lấy dư cho 1000007. Vậy theo một cách đơn giản như trên có thể sẽ có bạn code thế này:
Xem code cách 1 (bị tràn số)
#include <bits/stdc++.h>
using namespace std;
int Solve1(int n){
int s = 0;
for(int i = 1; i <= n; ++i){
s += i * (i + 1);
}
return s % 1000007;
}
int main(){
int n;
cin >> n;
cout << Solve1(n);
return 0;
}Nếu bạn nào làm như thế này thì rất tiếc phải chia buồn là code bạn chắc chắn có lỗi. Tại vì sao? Các bạn thử xem, theo như đề bài thì tối đa $N$ có thể lên đến $10^9$, giờ giả sử cho $N = 100000$ ($10^5$) nhé, nếu thế đáp án đúng chạy phải ra là 13000, nhưng các bạn thử nhập $N = 10^5$ rồi xem code ở trên sẽ ra đáp án bao nhiêu? Chắc chắn không phải là 13000 (mình chạy thử thì nó in ra hẳn một số âm: −330707). Thì tại sao lại như vậy? Bởi vì nó đã bị tràn số, từ đó ra kết quả sai đấy.
Các bạn thử xem, cuối cùng của $S$ là sẽ cộng với $N \times (N+1)$, giờ giả sử chỉ tính riêng phần này thôi, tức là khi $N = 10^5$ thì chỗ này sẽ là $10^5 \times (10^5 + 1)$, tức là hơn cả $10^{10}$, chưa kể là còn cộng với cả 1 đống trước đó nữa: $1 \times 2 + 2 \times 3 + \ldots + (N-1) \times N$ thì kết quả càng lớn hơn rất nhiều. Nên nếu các bạn dùng kiểu dữ liệu int là kiểu số nguyên 4 byte để lưu trữ cho biến s thì chắc chắn là sẽ bị tràn số, bởi kiểu số nguyên 4 byte có dấu (có cả âm) tối đa cũng chỉ lưu được đến hơn $2 \times 10^9$, kiểu không dấu (chỉ có dương) tối đa cũng chỉ lưu được đến hơn $4 \times 10^9$. Trong khi đó kết quả cần lưu ở đây là lớn hơn $10^{10}$ rất nhiều nên chắc chắn biến s sẽ bị tràn số. Vậy nên ở đây ta cần lưu trữ biến s theo kiểu số nguyên 8 byte như kiểu long long, lúc này kiểu long long có thể lưu trữ đến hơn $9 \times 10^{18}$ vì thế ta có thể yên tâm trong trường hợp này.
s thành kiểu long long và nghĩ rằng thế là đủ thì các bạn cũng nhầm to. Các bạn có thể thử chạy lại với $N = 100000$ thì đáp án cũng vẫn không ra 13000 đâu. Bởi vì sao lại như vậy? Nhiều bạn không biết điều này: đó là các bạn chú ý phép tính i * (i + 1) của các bạn trong vòng lặp, quy trình nó xử lý là nó sẽ luôn lưu trữ lại các giá trị tính toán tạm thời vào những vùng nhớ tạm được hệ thống tự động sinh ra, rồi sau cùng giá trị cuối cùng mới được gán qua s. Như trường hợp này đầu tiên nó sẽ tính i + 1 lưu trữ kết quả này vào vùng nhớ tạm, rồi thì lấy kết quả của vùng nhớ tạm đó nhân tiếp với i và kết quả lại tiếp tục được lưu trữ vào vùng nhớ tạm khác nữa. Rồi sau cùng kết quả của vùng nhớ tạm đó mới được gán qua biến s. Thì vấn đề là các vùng nhớ tạm này khi được sinh ra tự động nó sẽ căn cứ theo kích thước của các biến thành phần tham gia phép tính mà sinh ra kích thước vùng nhớ tạm theo đó, thì như hiện tại biến i đang có kiểu là int vì thế các vùng nhớ tạm này cũng sẽ là kiểu int, từ đó khiến bị tràn số như đã nói ở trên, vì khi $i = 10^5$ thì $10^5 \times (10^5 + 1)$ kiểu int làm sao chứa nổi. Vậy nên các bạn phải sửa lại cho biến i thành kiểu long long luôn nhé.Như thế thì mới hết bị tràn số và cho ra kết quả chính xác. Còn kết quả trả về của hàm vẫn để kiểu int được là bởi vì sau cùng đáp án sẽ chia lấy dư cho $(10^6 + 7)$ thì phần kết quả chắc chắn sẽ nhỏ hơn $(10^6 + 7)$, vì thế kiểu trả về int có thể chứa được, cũng như biến n ta vẫn có thể để kiểu int vì tối đa theo như đề công bố nó cũng chỉ $10^9$ nên vẫn nằm trong phạm vi của kiểu int. Còn lại thì biến tổng s cũng như biến i duyệt trong vòng lặp các bạn phải để kiểu long long thì mới không bị sai nhé.
long long, kiểu số thực các bạn hãy dùng kiểu 8 byte hết tức là double, để nó không sợ bị tràn số làm sai chương trình. Bộ nhớ lúc nào cũng luôn cho dư dả thoải mái nên ta không sợ tốn bao nhiêu cả vì đây chỉ là những biến lẻ. Còn lại thì nếu trong tình huống ta cần khởi tạo mảng 1 chiều có nhiều số thì lúc này đúng là ta phải cân nhắc từng phần tử trong mảng nên là kiểu 4 byte hay 8 byte, vì lúc này nó sẽ làm cho tổng bộ nhớ tăng lên đáng kể khi mảng có nhiều phần tử. Còn nếu là các biến lẻ tẻ như trong bài này thì cứ cho hết kiểu 8 byte cho chắc nhé các bạn.Để thấy rõ cái bẫy tràn số, em nhập $N$ rồi bấm Tiếp: tổng $S$ tăng rất nhanh (khoảng $N^3/3$), xem nó vượt sức chứa của int rồi của long long lúc nào, trong khi phần dư $S \% 1000007$ thì lúc nào cũng nhỏ:
90%Cách 2: sửa lại kiểu long long
Vậy code ở trên để không bị tràn số thì nên sửa lại thế này:
Xem code cách 2
#include <bits/stdc++.h>
using namespace std;
long long Solve2(long long n){
long long s = 0;
for(long long i = 1; i <= n; ++i){
s += i * (i + 1);
}
return s % 1000007;
}
int main(){
long long n;
cin >> n;
cout << Solve2(n);
return 0;
}def Solve2(n):
s = 0
for i in range(1, n + 1):
s += i * (i + 1)
return s % 1000007
n = int(input())
print(Solve2(n))Đến đây các bạn đừng nghĩ là đã xong nhé, bài này không đơn giản như vậy đâu. Ta hãy để ý rằng: đề bài yêu cầu kết quả tổng $S$ sau cùng sẽ chia lấy dư cho 1000007 ($10^6 + 7$). Ta phải suy nghĩ xem vì sao lại phải có yêu cầu này? Thì nếu bạn nào đã gặp phải dạng này thì sẽ biết, bình thường trong các đề bài cũng luôn nói rõ lý do vì sao phải như vậy, còn trong bài này thì không thấy nói, chắc là cố tình không nói để gài bẫy bạn nào không biết đấy hehe. Bình thường câu kèm theo luôn là: "Vì kết quả có thể rất lớn nên chỉ cần lấy phần dư của phép chia kết quả cho số C nào đó", như trong bài này C là 1000007.
Vậy ta chú ý: "Kết quả có thể rất lớn" nên mới cần chia lấy dư. Nếu bạn nào không biết thì chỗ này sẽ suy nghĩ: đằng nào chẳng tính ra kết quả rồi thì tại sao không in kết quả đó ra luôn mà phải làm thêm bước chia lấy dư làm gì? Có in kết quả ra thôi thì cứ in bình thường, bộ chẳng lẽ lớn thì không in được sao? Đó là với những bạn nào không biết về các phép toán modular.
Các bạn hãy chú ý phần giới hạn nhé, $N$ tối đa có 3 mức độ: $10^3$, $10^6$, $10^9$. Các bạn thử suy nghĩ giả sử trong tình huống $N = 10^9$ hen, thì lúc này nội ở lần cuối cùng đi tính $N \times (N+1)$, tức là $10^9 \times (10^9 + 1)$ thì nó đã lên hơn $10^{18}$, là tiệm cận với độ lớn kiểu dữ liệu số nguyên 8 byte mà ngôn ngữ C/C++ hỗ trợ rồi, chưa kể còn phải cộng tổng của 1 mớ trước đó nữa. Thì lúc này nếu trong trường hợp $N = 10^9$ chắc chắn sẽ không thể nào lưu trữ được kết quả khổng lồ này (khoảng $3.3 \times 10^{26}$) với những kiểu dữ liệu số nguyên được hỗ trợ sẵn trong C/C++. Vậy nên rõ ràng nếu các bạn mà làm theo đúng quy trình đi tính ra được tổng thì không thể lưu trữ nổi tổng này với những kiểu dữ liệu có sẵn, lúc này nếu muốn các bạn phải tự xây dựng kiểu dữ liệu số nguyên lớn (bài toán Big Int), lúc này nó lại phức tạp vấn đề thêm.
90%Cách 3: áp dụng các phép toán modular
Vậy nên nếu đề bài mà không nói đến việc kết quả chia lấy dư thì chắc chắn các bạn phải tự xây dựng bài toán Big Int để xử lý số nguyên lớn như mình nói ở trên. Còn lại khi đề đã cho phép chỉ cần in ra kết quả sau cùng chia lấy dư cho 1 số C nào đó là được, thì nó đã mở đường cho ta đơn giản hóa bài toán đi nếu các bạn biết về các phép toán modular sau đây, các bạn chú ý xem kỹ nhé:
- Quy tắc cộng: (a + b) % c = ((a % c) + (b % c)) % c
- Quy tắc trừ: (a - b) % c = ((a % c) - (b % c)) % c
- Quy tắc nhân: (a * b) % c = ((a % c) * (b % c)) % c
Với $a$, $b$ là 2 số nguyên cần tính toán, $c$ là số mà ta sẽ chia lấy dư cho nó.
(a % c) - (b % c) có thể ra số âm, mà phép % trong C/C++ với số âm sẽ cho kết quả âm. Nên khi code thì ta hay viết ((a % c) - (b % c) + c) % c để kết quả luôn nằm trong đoạn từ 0 đến $c - 1$ nhé.Các bạn thử xem nhé, ví dụ khi $a = 37$, $b = 59$, $c = 3$. Thay vì bình thường ta phải lấy $37 \times 59 = 2183$ rồi thì $2183 \% 3 = 2$. Trong khi đó nếu áp dụng theo công thức ở trên ta sẽ có: $37 \% 3 = 1$, $59 \% 3 = 2$, rồi thì $(1 \times 2) \% 3$ tức $2 \% 3 = 2$.
2183 % 3 = 2
(1 × 2) % 3 = 2
Ta thấy không cần phải lưu trữ tính toán đến giá trị lớn như 2183 mà chỉ cần lấy chính các giá trị tham số $a$, $b$ ban đầu tính với nhau mà vẫn ra được kết quả đúng. Đây là cách để ta giảm thiểu độ lớn số cần phải lưu trữ nhưng vẫn ra được kết quả sau cùng đúng.
Vậy nên áp dụng phép toán modular vào code ở trên, ta thấy rằng s = s + (i * (i + 1)). Nghĩa là ta có thể áp dụng quy tắc cộng vào với a = s, b = i * (i + 1). Rồi nếu áp dụng quy tắc cộng vào thì có phải ta sẽ cần tính b % c đúng không? Thì lúc này b đang là phép nhân giữa i và (i + 1) nên chỗ này nó lại áp dụng quy tắc nhân với a = i, b = i + 1 các bạn thấy không? Vậy nếu muốn xử lý được số lớn thì ta phải áp dụng các phép toán modular vào, đoạn code ở trên sau khi áp dụng các phép toán modular vào sẽ là:
Xem code cách 3
#include <bits/stdc++.h>
using namespace std;
const long long c = 1000007;
long long Solve3(long long n){
long long s = 0;
for(long long i = 1; i <= n; ++i){
s += ((i % c) * ((i + 1) % c)) % c;
s %= c;
}
return s;
}
int main(){
long long n;
cin >> n;
cout << Solve3(n);
return 0;
}c = 1000007
def Solve3(n):
s = 0
for i in range(1, n + 1):
s += (i % c) * ((i + 1) % c)
s %= c
return s
n = int(input())
print(Solve3(n))Nếu bạn nào làm đến đây thì các bạn đã được 90% điểm của bài này, hoặc may mắn thì 95%, nhưng chắc chắn sẽ còn lại một ngưỡng % nhỏ còn lại các bạn sẽ không lấy được, nghĩa là các bạn sẽ không được full điểm của bài này. Lý do là vì code ở trên có độ phức tạp thời gian là $O(N)$, tức là cần lặp qua $N$ lần. Và như mình hay nói, với thời gian chạy giới hạn 1 giây thì số lần lặp tối đa được phép chỉ nên ở ngưỡng $(3 \div 5) \times 10^7$ hay cao lắm là $10^8$ lần. Trong khi đó các bạn xem đề có nói rõ 10% số test cuối cùng sẽ là những trường hợp $N \le 10^9$. Vậy nghĩa là nếu $N$ từ $10^8$ trở lên đến $10^9$ thì code này sẽ bị chạy quá giới hạn thời gian (mình chạy thử với $N = 10^9$ thì mất khoảng 4.6 giây). Còn 90% test là từ $10^6$ trở xuống thì code ở trên yên tâm sẽ ổn.
Ghi chú thêm: với $N \le 10^6$ thì tổng $S$ tối đa chỉ khoảng $3.3 \times 10^{17}$, vẫn vừa kiểu long long, nên thực ra code cách 2 cũng qua được 90% test này. Phép toán modular sẽ trở nên bắt buộc ở bước tiếp theo, khi ta dùng công thức để tính thẳng với $N = 10^9$.
100%Cách 4: công thức tổng quát, O(1)
Vậy lúc này ta phải xem có cách nào để nhanh chóng tính ra được đáp án kể cả với trường hợp tối đa $N = 10^9$ hay không, mà không cần phải lặp đủ $N$ lần? Thì rõ ràng ta có thể nhìn ra nếu với những phép tính mà nó có một quy luật ta nhìn thấy được, như trường hợp này sẽ luôn là $i \times (i + 1)$ với $i$ tăng dần từ 1 đến $N$ và tính tổng tụi nó lại, quy tắc này quá rõ ràng để nhìn ra. Các bạn cứ nhớ thường cái gì đã có quy tắc thì lúc nào nó cũng có công thức tổng quát để rút gọn nhanh chóng tính ra được đáp án mà không cần phải đi lặp tính từng cái một vậy đó.
Vậy nếu bạn nào đã biết trước về công thức này, hay các bạn nào nếu chưa biết nhưng trong thời gian thi mà có thể tìm ra được thì đây là mấu chốt để các bạn được trọn 100% điểm. Công thức tổng quát đó chính là:
Các bạn hãy thử tính vài trường hợp xem công thức này có đúng không?
| N | Cộng từng số hạng | Công thức N(N+1)(N+2)/3 | |
|---|---|---|---|
| 1 | 1×2 = 2 | (1×2×3) / 3 = 6 / 3 = 2 | ✓ |
| 2 | 1×2 + 2×3 = 8 | (2×3×4) / 3 = 24 / 3 = 8 | ✓ |
| 3 | 1×2 + 2×3 + 3×4 = 20 | (3×4×5) / 3 = 60 / 3 = 20 | ✓ |
| 4 | 1×2 + 2×3 + 3×4 + 4×5 = 40 | (4×5×6) / 3 = 120 / 3 = 40 | ✓ |
| 5 | 1×2 + 2×3 + 3×4 + 4×5 + 5×6 = 70 | (5×6×7) / 3 = 210 / 3 = 70 | ✓ |
Còn nếu bạn nào giờ mới biết thì các bạn có thể Google search tìm hiểu cách chứng minh vì sao lại có công thức này nhé, nó cũng đơn giản thôi. Từ khóa cho các bạn: formula 1*2 + 2*3 + 3*4 + ... + n*(n+1).
Xem chứng minh nhanh
Để ý rằng mỗi số hạng có thể viết thành hiệu của 2 tích 3 số liên tiếp:
Cộng tất cả các số hạng với $i$ từ 1 đến $N$, các tích ở giữa triệt tiêu lẫn nhau (kiểu "tổng lồng nhau"), chỉ còn lại $\frac{N(N+1)(N+2) - 0}{3}$. Vậy $S = \frac{N(N+1)(N+2)}{3}$.
Vậy nếu áp dụng công thức này vào thì bài này ta có thể rút độ phức tạp thời gian từ $O(N)$ xuống chỉ còn $O(1)$. Nếu áp dụng vào thì ta hiểu kết quả sau cùng sẽ là: ((n*(n+1)*(n+2))/3) % c.
(a / b) % c = ((a % c) / (b % c)) % c là không đúng nha, các bạn thử thế số vào là thấy ngay nó sai.Vậy nên trong trường hợp này cần ứng dụng modular vào công thức này làm sao? Thì ta thấy rằng khi công thức tổng quát đã cho biết đáp án sẽ là $\frac{n(n+1)(n+2)}{3}$, nghĩa là chắc chắn kết quả tích của 3 số $n$, $n+1$, $n+2$ nhân nhau lại sẽ tạo thành số có thể chia hết cho 3 (trong 3 số nguyên liên tiếp luôn có 1 số chia hết cho 3). Vậy:
- Nếu xét thấy $n$ chia hết cho 3 thì ta sẽ lấy $n$ chia luôn cho 3 để triệt tiêu luôn mẫu số, lúc này ta có thể tạo biến
a = n / 3vàbsẽ là tích của 2 số còn lại, tức làb = (n + 1) * (n + 2). Rồi thì lúc này quy chuẩn về lại phép tính(a * b) % c. - Còn nếu xét thấy $n$ không chia hết cho 3 thì ta chắc chắn rằng phần tích 2 số còn lại, tức là $(n+1)(n+2)$, nó sẽ chia hết cho 3. Lúc đó ta sẽ lấy tích của chúng chia luôn cho 3 để triệt tiêu luôn mẫu số, lúc này ta có thể tạo biến
a = nvàb = ((n + 1) * (n + 2)) / 3, rồi thì lúc này lại quy chuẩn về phép tính(a * b) % c.
Nếu làm như vậy thì ta thấy a hay b tối đa sẽ là tích của 2 số, như thế giả sử khi $N$ tối đa là $10^9$ thì tích của 2 số sẽ là $10^{18}$, vẫn trong phạm vi lưu trữ được. Rồi thì % c là % (10^6 + 7), lúc này kết quả nó sẽ ra số đảm bảo nhỏ hơn $10^6 + 7$ vì đó là quy luật của phép chia dư: khi % x thì kết quả sẽ luôn trong đoạn từ 0 đến $x - 1$. Lúc này sau khi a % c và b % c thì chúng nhân nhau thì tối đa sẽ ra khoảng $10^{12}$, vẫn là số lưu trữ được, và rồi từ đó % c thêm lần nữa là ra đáp án bài toán.
Source code cho các bạn tham khảo nếu làm theo cách này:
#include <bits/stdc++.h>
using namespace std;
const long long c = 1000007;
long long Solve4(long long n){
long long a, b;
if(n % 3 == 0){
a = n / 3;
b = (n + 1) * (n + 2);
}
else{
a = n;
b = ((n + 1) * (n + 2)) / 3;
}
return ((a % c) * (b % c)) % c;
}
int main(){
long long n;
cin >> n;
cout << Solve4(n);
return 0;
}c = 1000007
def Solve4(n):
if n % 3 == 0:
a = n // 3
b = (n + 1) * (n + 2)
else:
a = n
b = ((n + 1) * (n + 2)) // 3
return (a % c) * (b % c) % c
n = int(input())
print(Solve4(n))Với cách làm này thì độ phức tạp thời gian (Time Complexity) lẫn độ phức tạp không gian (Space Complexity) đều là $O(1)$, tức là độ phức tạp hằng số. Và đây là cách làm tối ưu nhất, không thể có cách nào khác tối ưu hơn được. Nên với độ phức tạp này thì yên tâm sẽ không sợ bị TLE, vì lúc này nó không biến thiên theo giá trị $N$, dù $N$ có là bao nhiêu thì chỉ cần vài phép tính là ra đáp án ngay lập tức, hoàn toàn không cần chạy vòng lặp gì cả.
Tổng kết
| Cách | Ý tưởng | Độ phức tạp | Kết quả |
|---|---|---|---|
| 1 | Vòng lặp, biến int | O(N) | Sai do tràn số |
| 2 | Vòng lặp, biến long long | O(N) | 90% |
| 3 | Vòng lặp + phép toán modular | O(N) | 90% (TLE với N = 10^9) |
| 4 | Công thức N(N+1)(N+2)/3 + modular | O(1) | 100% |
Đến đây các bạn nhìn lại xem, mình đã giải cả thảy 4 cách từ cách tệ nhất đến tối ưu dần lên. Và ta có thể thấy nếu bài này bạn nào mà không biết các phép toán modular hoặc không biết công thức rút gọn thì sẽ không thể giải trọn vẹn bài này rồi. Vậy nên tuy nói bài này là cho điểm nhưng mà cũng là cho điểm với những ai biết các công thức toán học này hihi.
Nhận xét
Đăng nhận xét