Hướng dẫn giải của [CSES 3355] Sum of Four Squares
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.
Gọi ~N=10^7~ là giá trị lớn nhất của ~n~.
Đầu tiên ta tìm tất cả các số nguyên từ ~0~ đến ~N~ có thể biểu diễn thành tổng của hai bình phương. Việc này có thể thực hiện trong ~O(N)~ thời gian. Với mỗi số ~x=a^2+b^2~ như vậy, ta lưu số thứ nhất ~a~ và số thứ hai ~b~.
Sau đó, ta có thể tìm nghiệm cho mọi ~n~ trong ~O(n)~ thời gian bằng cách tìm một số ~x~ sao cho cả ~x~ và ~n-x~ đều có thể biểu diễn thành tổng của hai bình phương. Có thể chứng minh rằng luôn tồn tại nghiệm.
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e7;
int main() {
int t;
cin >> t;
vector<bool> can(N + 1);
vector<int> first(N + 1), second(N + 1);
for (int a = 0; a * a <= N; a++) {
for (int b = 0; a * a + b * b <= N; b++) {
int x = a * a + b * b;
can[x] = true;
first[x] = a;
second[x] = b;
}
}
while (t--) {
int n;
cin >> n;
for (int x = 0; x <= n; x++) {
if (can[x] && can[n - x]) {
cout << first[x] << " " << second[x] << " ";
cout << first[n - x] << " " << second[n - x] << "\n";
break;
}
}
}
}
Tài liệu tham khảo
Chương trình tham khảo
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e7;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
vector<bool> can(N + 1);
vector<int> first(N + 1), second(N + 1);
for (int a = 0; a * a <= N; a++) {
for (int b = 0; a * a + b * b <= N; b++) {
int x = a * a + b * b;
can[x] = true;
first[x] = a;
second[x] = b;
}
}
while (t--) {
int n;
cin >> n;
for (int x = 0; x <= n; x++) {
if (can[x] && can[n - x]) {
cout << first[x] << " " << second[x] << " ";
cout << first[n - x] << " " << second[n - x] << "\n";
break;
}
}
}
}
Bình luận