Editorial for ptit011: Mật mã!

Hiểu bài toán

Bài toán yêu cầu xác định xem một số nguyên dương $n$ ($0 \le n \le 10^{17}$) có thể được biểu diễn dưới dạng số tam giác cân hay không.

Từ lời nói của nhân vật: 'Nếu từ $n$ chấm tròn có thể xếp thành hình tam giác cân với độ dài cạnh $h \ge 2$...'.

Ta phân tích hình tam giác cân:

• Đỉnh là 1 chấm.
• Hai bên sườn mỗi bên có $h-1$ chấm.
• Đáy có $h$ chấm.

Tổng số chấm $n$ là: $n = \text{Đỉnh} + \text{2 bên sườn} + \text{Đáy}$ $n = 1 + 2(h-1) + h$ $n = 1 + 2h - 2 + h$ $n = 3h - 1$

Vậy bài toán quy về việc kiểm tra xem có tồn tại số nguyên $h \ge 2$ sao cho $n = 3h - 1$ hay không.

Ngoài ra, các giải pháp tham khảo còn đề cập đến trường hợp 'tam giác đều' (equilateral triangle) như một cách giải thích khác hoặc một trường hợp đặc biệt. Tam giác đều $h \times h$ chấm: $n = h^2$ với $h \ge 2$.

Nếu chỉ xét theo mô tả 'tam giác cân', ta chỉ cần kiểm tra công thức $3h-1$. Tuy nhiên, các giải pháp Accepted đều kiểm tra cả hai khả năng:

1. $n$ là bình phương của một số nguyên $h \ge 2$ (tương ứng với hình vuông/chữ nhật hoặc tam giác đều).
2. $n$ có thể viết dưới dạng $3h-1$ với $h \ge 2$ (hình tam giác cân).

Do đó, để chắc chắn, ta sẽ xử lý cả hai trường hợp này.

Các cách tiếp cận

Cách Giải thích Toán học (Phân tích công thức)

#include <stdio.h>
#include <math.h>

int main() {
    long long n;
    scanf("%lld", &n);

    // Kiểm tra điều kiện h >= 2
    // Trường hợp 1: n = h^2 (Tam giác đều/vuông)
    // => h = sqrt(n)
    // Ta cần sqrt(n) là số nguyên và >= 2 (tức n >= 4)

    // Trường hợp 2: n = 3h - 1 (Tam giác cân)
    // => 3h = n + 1
    // => h = (n + 1) / 3
    // Ta cần (n + 1) chia hết cho 3 và kết quả >= 2
    // Điều này tương đương: (n + 1) % 3 == 0 và (n + 1) / 3 >= 2

    long long h_square = (long long)sqrt(n);
    long long h_triangle = (n + 1) / 3;

    int is_square = (h_square * h_square == n && h_square >= 2);
    int is_triangle = ((n + 1) % 3 == 0 && h_triangle >= 2);

    if (is_square || is_triangle) {
        printf("YES");
    } else {
        printf("NO");
    }

    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất dựa trên phân tích hình học. Tác giả nhận diện hai cấu trúc có thể tạo ra:

1. Hình vuông/Tam giác đều: Tổng số chấm là $h^2$. Ta chỉ cần kiểm tra xem $n$ có phải là số chính phương ($h \ge 2$) hay không.
2. Hình tam giác cân: Tổng số chấm là $3h-1$. Ta cần kiểm tra xem $n+1$ có chia hết cho 3 không, và thương số $h = (n+1)/3$ có lớn hơn hoặc bằng 2 không. Cách này rất hiệu quả và dễ hiểu, sử dụng phép chia và kiểm tra số học đơn giản.

Cách Sử dụng công thức nghiệm phương trình bậc nhất

#include <stdio.h>
#include <math.h>

int main() {
    long long n;
    scanf("%lld", &n);

    // Kiểm tra tam giác đều (n = h^2)
    long long h = sqrt(n);
    if (h * h == n && h >= 2) {
        printf("YES");
        return 0;
    }

    // Kiểm tra tam giác cân (n = 3h - 1)
    // Ta cần tìm h là số nguyên: h = (n + 1) / 3
    // Hoặc có thể dùng phương trình: 3h - n = 1
    // Dùng hàm sqrt để kiểm tra tính chính xác của số học (như trong code tham khảo)

    // Code tham khảo dùng: sqrt(1 + 8*n) hoặc sqrt(4*n)
    // Thực chất sqrt(4*n) là để kiểm tra n có phải số chính phương không (phép biến đổi hình vuông)
    // Nhưng ở đây ta đã kiểm tra rồi.

    // Chỉ cần kiểm tra n = 3h - 1:
    if ((n + 1) % 3 == 0) {
        long long h_val = (n + 1) / 3;
        if (h_val >= 2) {
            printf("YES");
            return 0;
        }
    }

    printf("NO");
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Cách tiếp cận này giải phương trình cấp 1 để tìm số lượng cạnh $h$.

• Để $n = h^2$, ta cần $\sqrt{n}$ là số nguyên.
• Để $n = 3h - 1$, ta cần $n \equiv -1 \pmod 3$ (tức $n \equiv 2 \pmod 3$). Các giải pháp tham khảo (Solution 1) có vẻ hơi rắc rối khi dùng sqrt(4*n) thay vì kiểm tra trực tiếp $n$ có phải số chính phương, nhưng mục đích là giống nhau. Logic cốt lõi là kiểm tra hai công thức $n = h^2$ và $n = 3h - 1$. Phương pháp này loại bỏ các trường hợp $n < 6$ ở bước điều kiện biên.

Cách Thử nghiệm với các giá trị biên (Brute Force)

#include <stdio.h>

int main() {
    long long n;
    scanf("%lld", &n);

    // Vì n <= 10^17 nên h có thể rất lớn.
    // Brute force trực tiếp từ 1 lên là không khả thi.
    // Tuy nhiên, ta có thể dùng công thức suy ra h.
    // Đơn giản nhất là giải phương trình.

    // Kiểm tra n = h^2
    long long h = 1;
    while (h * h < n) {
        h++;
        if (h > 100000000) break; // Tránh tràn số nếu dùng loop
    }
    // Thay vào đó, dùng hàm sqrt là tốt nhất
    // Code này chỉ để minh họa logic 'thử giá trị h'

    // Đúng ra nên dùng:
    // long long root = sqrt(n);
    // if (root*root == n && root >= 2) YES

    // Logic cho tam giác cân:
    // n = 3h - 1 => h = (n+1)/3
    // Nếu (n+1) chia hết cho 3 và h >= 2 => YES

    if (n < 6) {
        printf("NO");
        return 0;
    }

    long long root = (long long)sqrt(n);
    if (root * root == n && root >= 2) {
        printf("YES");
        return 0;
    }

    if ((n + 1) % 3 == 0 && (n + 1) / 3 >= 2) {
        printf("YES");
        return 0;
    }

    printf("NO");
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Mặc dù gọi là 'Brute Force', nhưng do giới hạn $n$ quá lớn ($10^{17}$), việc lặp từ 1 để tìm $h$ là không thể. Thay vào đó, ta phải dùng các công thức toán học để 'thử' ngay giá trị $h$.

• Thử $h$ cho hình vuông: $h = \sqrt{n}$.
• Thử $h$ cho tam giác cân: $h = (n+1)/3$. Nếu các giá trị $h$ này là số nguyên và thỏa mãn điều kiện $h \ge 2$, ta có đáp án. Đây thực chất là cách tiếp cận dạng số học.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể được chia thành 2 trường hợp con độc lập dựa trên hình dạng: Tam giác đều/vuông ($n = h^2$) và Tam giác cân ($n = 3h - 1$).
• Do $n$ lên tới $10^{17}$, các thuật toán lặp tuần tự sẽ超时. Cần sử dụng các phép toán số học trực tiếp (bình phương căn, phép chia, phép tính dư).
• Điều kiện $h \ge 2$ rất quan trọng, loại các trường hợp $n=1$ (h=1) hoặc $n=2$ hay $n=5$ ($h=2$ cho tam giác cân $3*2-1=5$ là YES, nhưng $n=2$ thì không có công thức nào cho $h \ge 2$).

Lỗi thường gặp

• Sai lệch trong công thức tam giác cân: Có thể nhầm $n = 3h - 1$ với $n = \frac{h(h+1)}{2}$ (tam giác đều - không phải hình học trong bài này).
• Overflow số: Khi tính toán, cần dùng kiểu dữ liệu 64-bit (long long ở C/C++) vì $n$ có thể lên tới $10^{17}$, và nếu tính $h^2$ cần kiểm tra kỹ.
• Bỏ qua điều kiện $h \ge 2$: Ví dụ $n=1$ (h=1) hoặc $n=2$ (không có $h$ nguyên thỏa) cần in ra NO.