Hướng dẫn giải của [200 đề thầy Đức] Bài 54: Số tam giác
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Kiểm tra số ~A~ có viết được thành tổng của hai số tam giác (~K(K+1)/2~ với ~K \ge 1~) hay không.
Sub 1: Vét cạn cặp số tam giác — ~O(m^2)~ với ~m \approx \sqrt{2A}~, dùng khi ~A \le 10^5~
Liệt kê mọi số tam giác không lớn hơn ~A~ rồi thử mọi cặp (có thể trùng nhau). Nếu có cặp có tổng bằng ~A~ thì in YES.
Nếu chỉ nộp sub này: đúng 99/99 test.
Sub 2: Kiểm tra từng phần bù — ~O(\sqrt{A})~, dùng khi mọi trường hợp còn lại
Với mỗi số tam giác ~T_a < A~, kiểm tra ~A - T_a~ có là số tam giác không. Số ~x~ là tam giác khi và chỉ khi ~8x+1~ là số chính phương lẻ, nên kiểm tra được bằng căn bậc hai. Dùng số nguyên 64 bit vì ~8A+1~ có thể lớn.
Nếu chỉ nộp sub này: đúng 99/99 test.
Chương trình hoàn chỉnh
Chương trình đọc ~T~ rồi từng ~A~. Nếu ~A \le 10^5~ thì gọi sub1, ngược lại gọi sub2. Hai số hạng có thể bằng nhau, ví dụ ~2 = 1 + 1~ nên đáp án YES. Số ~A~ là số tam giác nhưng không tách được thành tổng của hai số tam giác dương thì vẫn NO.
#include <bits/stdc++.h>
using namespace std;
long long A; // so can kiem tra
// Kiem tra x co phai so tam giac (1, 3, 6, 10, ...) hay khong.
// x = k(k+1)/2 <=> 8x+1 la so chinh phuong le.
bool isTri(long long x) {
if (x <= 0) return false;
long long v = 8 * x + 1;
long long r = (long long)sqrtl((long double)v);
while (r * r > v) r--;
while ((r + 1) * (r + 1) <= v) r++;
return r * r == v && r % 2 == 1;
}
// Sub 1: vet can. Liet ke cac so tam giac <= A, thu moi cap (x, y) co x + y = A.
// O(m^2) voi m ~ sqrt(A), dung khi A <= 10^5.
void sub1() {
vector<long long> t;
for (long long a = 1; a * (a + 1) / 2 <= A; a++) t.push_back(a * (a + 1) / 2);
for (long long x : t)
for (long long y : t)
if (x + y == A) {
cout << "YES\n";
return;
}
cout << "NO\n";
}
// Sub 2: voi moi so tam giac T_a < A, kiem tra A - T_a co la so tam giac khong. O(sqrt(A)).
void sub2() {
for (long long a = 1; a * (a + 1) / 2 < A; a++)
if (isTri(A - a * (a + 1) / 2)) {
cout << "YES\n";
return;
}
cout << "NO\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> A;
if (A <= 100000) sub1();
else sub2();
}
return 0;
}
Bình luận