Hướng dẫn giải của [200 đề thầy Đức] Bài 6: 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
Số N là số tam giác nếu tồn tại k sao cho N = 1 + 2 + ... + k = k(k+1)/2. Với mỗi N cần kiểm tra điều này.
Sub 1: Thử từng hàng — ~O(\sqrt{N})~
Duyệt k = 1, 2, ... cho đến khi k(k+1)/2 vượt quá N. Nếu có k nào cho đúng N thì in 1, ngược lại in 0. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long n;
cin >> n;
bool ok = false;
// Vét cạn: thử từng hàng k = 1, 2, ... cho đến khi tổng k(k+1)/2 vượt quá N
for (long long k = 1; k * (k + 1) / 2 <= n; k++)
if (k * (k + 1) / 2 == n) ok = true;
cout << (ok ? 1 : 0) << "\n";
}
return 0;
}
Sub 2: Công thức căn bậc hai — ~O(1)~
Từ N = k(k+1)/2 suy ra 8N + 1 = (2k+1)^2, nên N là số tam giác khi và chỉ khi 8N + 1 là số chính phương. Tính căn nguyên của 8N + 1 rồi kiểm tra bình phương, dùng số nguyên 64-bit và chỉnh căn sau khi tính để tránh sai số. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long n;
cin >> n;
// N = k(k+1)/2 <=> 8N + 1 = (2k+1)^2 là số chính phương
long long m = 8 * n + 1;
long long s = (long long)sqrtl((long double)m);
while (s * s > m) s--; // chỉnh căn nguyên cho chính xác
while ((s + 1) * (s + 1) <= m) s++;
cout << (s * s == m ? 1 : 0) << "\n";
}
return 0;
}
Bình luận