Đếm đoạn (HNOI19_R1_DEMDOAN) (HSG Hà Nội 2019 vòng 1)

Nguồn: HNOJ – HSG Hà Nội 2019 vòng 1 (bài 1) Độ khó: Trung bình Toán học Ước số Hai con trỏ

Đề bài

Đếm đoạn

Cho số nguyên dương $N$. Đếm xem có bao nhiêu cặp số nguyên $a, b$ $(0 \lt a \le b)$ để tổng các số nguyên trong đoạn $[a, b]$ bằng $N$. Hai đoạn khác nhau là hai đoạn có ít nhất một phần tử khác nhau.

Dữ liệu vào từ tệp BAI1.INP: Gồm duy nhất một số nguyên dương $N$ $(0 \lt N \lt 10^{15})$.

Kết quả ra ghi vào tệp BAI1.OUT: Gồm một số nguyên dương duy nhất là kết quả của bài toán.

(Trên hệ thống chấm online thì đọc từ bàn phím và in ra màn hình như bình thường nhé.)

Lưu ý:

• Có 40% số điểm tương ứng với $N \le 10^4$.
• Có 30% số điểm tương ứng với $10^4 \lt N \le 10^8$.

BAI1.INP

9

BAI1.OUT

3

Giải thích

Có ba đoạn số thoả mãn:
[2, 4], [4, 5], [9, 9].

Lời mở đầu

Bài này mình được một em học viên hỏi: "Anh ơi cho em hỏi ý tưởng bài này với ạ. Số $N$ to thế này chắc là có mẹo nhìn ra hả anh? Bài này vét cạn thì em dùng 2 vòng for, rồi dùng công thức $(i + j)(j - i + 1)/2$ để tính tổng các số từ $i$ đến $j$, nếu bằng $N$ thì tăng đếm lên 1. Chỉ được 40% thôi ạ". Mình đã code xong theo 3 cách và hướng dẫn chi tiết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại thành bài giải đầy đủ để các bạn tham khảo nhen 😇.

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

Giải thích ví dụ: với $N = 9$, các đoạn số nguyên dương liên tiếp có tổng bằng $9$ là $2 + 3 + 4 = 9$, $4 + 5 = 9$ và chỉ một số $9$ (đoạn $[9, 9]$). Còn $[1, 3]$ có tổng $6$, $[1, 4]$ có tổng $10$... đều không được. Vậy đáp án là 3.

Gợi ý nhỏ: em học viên đã nhìn ra công thức $(i + j)(j - i + 1)/2$ ngay từ đầu, vậy là gần tiến được tới cách 100% rồi đó 😉. Mình sẽ đi qua 3 cách: cách được 40% là $O(N^2)$, cách được 70% là $O(N)$, cách được 100% là $O(\sqrt{2N})$.

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

Cách 1Vét cạn 2 vòng lặp · 40%Cách 2Mảng cộng dồn + hai con trỏ · 70%Cách 3Phân tích 2N thành 2 ước · 100%

Cách 1Vét cạn điểm đầu, cộng dần điểm cuối – O(N²) · 40%

Cho $a$ chạy từ $1$ đến $N$ làm điểm đầu đoạn. Với mỗi $a$, cho $b$ chạy từ $a$ trở đi và cộng dần $b$ vào sum:

• Nếu sum == n thì tìm được một đoạn $[a, b]$, tăng res.
• Nếu sum > n thì cộng thêm nữa chỉ càng lớn hơn (toàn số dương), nên break luôn để sang điểm đầu $a$ tiếp theo.

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;

// O(N^2): 40%
long long solve1(long long n){
    long long res = 0;
    for(long long a = 1; a <= n; ++a){
        long long sum = 0;
        for(long long b = a; b <= n; ++b){
            sum += b;
            if(sum == n){
                res++;
            }
            else if(sum > n){
                break;
            }
        }
    }
    return res;
}

int main(){
    long long n;
    cin >> n;
    cout << solve1(n);
    return 0;
}

# O(N^2): 40%
def solve1(n):
    res = 0
    for a in range(1, n + 1):
        s = 0
        for b in range(a, n + 1):
            s += b
            if s == n:
                res += 1
            elif s > n:
                break
    return res


n = int(input())
print(solve1(n))

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

• Không gian: $O(1)$.
• Thời gian: hai vòng lặp lồng nhau, đánh giá thô là $O(N^2)$. Với $N \le 10^4$ thì chạy tức thì, ăn được 40% số điểm.

Không gian$O(1)$

Thời gian$O(N^2)$

Thật ra nhờ break nên nhanh hơn N² khá nhiều

Với điểm đầu $a$, vòng trong chỉ chạy khoảng $\dfrac{N}{a}$ bước là tổng đã vượt $N$ rồi, nên tổng số bước cỡ $N \cdot (1 + \frac{1}{2} + \frac{1}{3} + \ldots) \approx N \ln N$. Mình đo thử bản C++ với $N = 10^8$ mất khoảng 0.9 giây, sát nút giới hạn thông thường. Nhưng với $N$ tới $10^{15}$ thì vẫn chắc chắn TLE.

Cách 2Mảng cộng dồn + hai con trỏ – O(N) · 70%

Cách này dùng tư tưởng mảng cộng dồn. Ví dụ từ dãy $1, 2, 3, 4, 5, 6, 7, 8, 9$ ta có mảng cộng dồn (thêm phần tử đầu $a_0 = 0$):

i	0	1	2	3	4	5	6	7	8	9
a[i]	0	1	3	6	10	15	21	28	36	45

Muốn biết đoạn từ $L = 3$ đến $R = 6$ có tổng bao nhiêu, thay vì cộng $3 + 4 + 5 + 6 = 18$ thì ta tính $a[R] - a[L - 1] = a[6] - a[2] = 21 - 3 = 18$.

Biến đổi

Đoạn $[i, j]$ có tổng bằng $n$ $\iff a[j] - a[i - 1] = n \iff a[j] = n + a[i - 1]$.
Vậy với mỗi điểm đầu $i$, tính được $x = a[i - 1] + n$, cần tìm xem có tồn tại $j$ nào để $a[j] = x$ không.

Chỗ tìm $j$ này dùng hai con trỏ để chạy một lượt là xong: với mỗi $i$, đẩy $j$ tiến lên cho tới khi $a[j] \ge x$, kiểm tra $a[j] == x$ thì đếm. Sang $i$ tiếp theo thì $x$ chỉ tăng lên, nên $j$ chỉ cần chạy tiếp từ vị trí đã tìm thấy trước đó, chứ không cần quay lại $j = i$. Nếu $j$ đã vượt quá $n$ thì không còn đoạn nào nữa, dừng luôn.

Ví dụ $n = 9$: $i = 1$: $x = 0 + 9 = 9$, $j$ chạy tới $4$ ($a[4] = 10 \ge 9$), không bằng. $i = 2$: $x = 1 + 9 = 10$, $j$ vẫn ở $4$, $a[4] = 10$ ⇒ đoạn $[2, 4]$ ✅. $i = 3$: $x = 12$, $j$ tiến tới $5$ ($15$) – không. $i = 4$: $x = 15 = a[5]$ ⇒ đoạn $[4, 5]$ ✅... cứ thế đến $i = 9$: $x = 36 + 9 = 45 = a[9]$ ⇒ đoạn $[9, 9]$ ✅.

Coi chừng bộ nhớ

Bản đầu của mình dùng vector<long long> a(n + 1) để lưu mảng cộng dồn. Với $N = 10^8$ thì mảng này tốn khoảng 800 MB, dễ vượt giới hạn bộ nhớ. Vì dãy ở đây chính là $1, 2, 3, \ldots$ nên $a[i] = 1 + 2 + \ldots + i = \dfrac{i(i + 1)}{2}$, mình tính thẳng bằng hàm A(i) thay cho mảng, thuật toán giữ nguyên.

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;

// O(N): 70%
// a[i] = 1 + 2 + ... + i = i * (i + 1) / 2 (mảng cộng dồn của dãy 1, 2, 3, ...)
long long A(long long i){
    return i * (i + 1) / 2;
}

long long solve2(long long n){
    long long j = 1;
    long long res = 0;
    for(long long i = 1; i <= n; ++i){
        long long x = A(i - 1) + n;
        while(j <= n && A(j) < x){
            j++;
        }
        if(j > n){
            break;
        }
        if(A(j) == x){
            res++;
        }
    }
    return res;
}

int main(){
    long long n;
    cin >> n;
    cout << solve2(n);
    return 0;
}

# O(N): 70%
def A(i):
    # a[i] = 1 + 2 + ... + i (mảng cộng dồn của dãy 1, 2, 3, ...)
    return i * (i + 1) // 2


def solve2(n):
    j = 1
    res = 0
    for i in range(1, n + 1):
        x = A(i - 1) + n
        while j <= n and A(j) < x:
            j += 1
        if j > n:
            break
        if A(j) == x:
            res += 1
    return res


n = int(input())
print(solve2(n))

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

• Không gian: $O(1)$ (vì tính $a[i]$ bằng công thức).
• Thời gian: $i$ chạy tối đa $n$ lần, $j$ cũng chỉ tiến tối đa $n$ lần trong suốt quá trình ⇒ $O(N)$. Với $N \le 10^8$ thì C++ qua được (mình đo khoảng 0.26 giây), ăn 70%.

Không gian$O(1)$

Thời gian$O(N)$

Cách 3Phân tích 2N thành tích hai ước – O(√(2N)) · 100%

Công thức cấp số cộng: tổng từ $u_1$ đến $u_n$ bằng $\dfrac{n(u_1 + u_n)}{2}$, tức là $\dfrac{(\text{số lượng số}) \cdot (\text{số đầu} + \text{số cuối})}{2}$. Từ đó tổng các số liên tục từ $a$ đến $b$ là:

$$\frac{(b - a + 1)(a + b)}{2} = N \iff (b - a + 1)(a + b) = 2N$$

Vậy ta phân tích các cặp ước số $x_1, x_2$ của $2N$, tức là $x_1 \cdot x_2 = 2N$ với $x_1 \le x_2$, rồi đặt:

Giải hệ

$b - a + 1 = x_1$ và $a + b = x_2$.
Từ phương trình đầu: $a = b + 1 - x_1$. Thế vào phương trình sau: $b + 1 - x_1 + b = x_2 \iff 2b = x_2 + x_1 - 1 \iff b = \dfrac{x_2 + x_1 - 1}{2}$.
Tính ra được $b$ rồi thế lại là tính ra được $a = b + 1 - x_1$.

Một cặp ước $(x_1, x_2)$ cho ra một đoạn hợp lệ khi:

• $x_2 + x_1 - 1$ chia hết cho $2$ (để $b$ là số nguyên), tức là $x_1$, $x_2$ phải khác tính chẵn lẻ;
• $0 \lt a \le b$ (đề yêu cầu $a$ dương).

Vì $x_1 \le x_2$ nên chỉ cần cho $x_1 = i$ chạy từ $1$ đến $\sqrt{2N}$, gặp $i$ là ước của $2N$ thì $x_2 = 2N / i$. Mỗi đoạn $[a, b]$ hợp lệ ứng với đúng một cặp $(x_1, x_2)$ (độ dài $b - a + 1$ luôn $\le a + b$ vì $a \ge 1$), nên đếm cặp chính là đếm đoạn.

Với $N = 9$: $2N = 18$, các cặp ước là $(1, 18), (2, 9), (3, 6)$:

x1	x2	x1 + x2 − 1	b	a	Đoạn
1	18	18	9	9	[9, 9] ✅
2	9	10	5	4	[4, 5] ✅
3	6	8	4	2	[2, 4] ✅

Đủ 3 đoạn như đề. Các bạn tự nhập $N$ khác vào khung minh hoạ dưới đây để xem có cặp ước nào bị loại nhé (ví dụ $N = 8$ hay $N = 15$):

N

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;

// O(sqrt(2*N)): 100%
long long solve3(long long n){
    long long x = 2 * n;
    long long res = 0;
    for(long long i = 1; i * i <= x; ++i){
        if(x % i == 0){
            long long x1 = i;
            long long x2 = x / i;
            if((x2 + x1 - 1) % 2 == 0){
                long long b = (x2 + x1 - 1) / 2;
                long long a = b + 1 - x1;
                if(0 < a && a <= b){
                    res++;
                }
            }
        }
    }
    return res;
}

int main(){
    long long n;
    cin >> n;
    cout << solve3(n);
    return 0;
}

from math import isqrt


# O(sqrt(2*N)): 100%
def solve3(n):
    x = 2 * n
    res = 0
    # lọc trước các ước i <= sqrt(x) bằng list comprehension cho nhanh
    for x1 in [i for i in range(1, isqrt(x) + 1) if x % i == 0]:
        x2 = x // x1
        if (x2 + x1 - 1) % 2 == 0:
            b = (x2 + x1 - 1) // 2
            a = b + 1 - x1
            if 0 < a <= b:
                res += 1
    return res


n = int(input())
print(solve3(n))

Các bạn bấm chạy tay code C++ để xem từng dòng nhé:

C++▶ Chạy tay từng dòng codeCách 3: duyệt ước i của 2N, giải b = (x1 + x2 − 1) / 2, a = b + 1 − x1.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4// O(sqrt(2*N)): 100%

5long long solve3(long long n){

6 long long x = 2 * n;

7 long long res = 0;

8 for(long long i = 1; i * i <= x; ++i){

9 if(x % i == 0){

10 long long x1 = i;

11 long long x2 = x / i;

12 if((x2 + x1 - 1) % 2 == 0){

13 long long b = (x2 + x1 - 1) / 2;

14 long long a = b + 1 - x1;

15 if(0 < a && a <= b){

16 res++;

17 }

18 }

19 }

20 }

21 return res;

22}

23

24int main(){

25 long long n;

26 cin >> n;

27 cout << solve3(n);

28 return 0;

29}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(1)$.
• Thời gian: vòng lặp chạy $i$ tới $\sqrt{2N}$. Với $N \lt 10^{15}$ thì $\sqrt{2 \cdot 10^{15}} \approx 4.5 \cdot 10^7$ bước, mỗi bước chỉ là một phép chia lấy dư ⇒ chạy thoải mái trong 1 giây.

Không gian$O(1)$

Thời gian$O(\sqrt{2N})$

Dùng long long

$N$ tới $10^{15}$ và $2N$ tới $2 \cdot 10^{15}$ nên mọi biến x, i, x1, x2, a, b đều phải là long long; điều kiện i * i <= x cũng phải tính bằng long long.

Ghi chú của mình: code C++ và Python của cả 3 cách cho đúng output ví dụ của đề, và đã được so với code vét cạn cho mọi $N$ từ $1$ đến $150$, cùng 200 giá trị $N$ ngẫu nhiên tới $10^5$ – khớp hết. Thời gian đo được: cách 1 C++ với $N = 10^8$ khoảng 0.9 giây; cách 2 C++ với $N = 10^8$ khoảng 0.26 giây (bản Python chạy quá 40 giây nên Python chỉ hợp với $N$ nhỏ); cách 3 C++ với $N \approx 10^{15}$ khoảng 0.15 giây, bản Python khoảng 2.3 giây (có thể bị quá thời gian ở các test lớn nhất).

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 😇